图 书 馆
利用低树宽计算所有对最短路径Computing All-Pairs Shortest Paths by Leveraging Low Treewidth |
|
| 课程网址: | http://videolectures.net/icaps2011_planken_computing/ |
| 主讲教师: | Léon Planken |
| 开课单位: | 代尔夫特工业大学 |
| 开课时间: | 2011-07-21 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Considering directed graphs on n vertices and m edges with real (possibly negative) weights, we present two new, efficient algorithms for computing all-pairs shortest paths (APSP). These algorithms make use of directed path consistency (DPC) along a vertex ordering d. The algorithms run in O(n2wd) time, where wd is the graph width induced by this vertex ordering. For graphs of constant tree width, this yields O(n2) time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. We show empirically that also in many general cases, both constructed and from realistic benchmarks, the algorithms often outperform Johnson's algorithm, which represents the current state of the art with a run time of O(nm + n2log n). These algorithms can be used for temporal and spatial reasoning, e.g. for the Simple Temporal Problem (STP), which underlines its relevance to the planning and scheduling community. |
| 关 键 词: | 常数树宽度图; 约翰逊算法; 空间推理; 时间问题 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-09-28：heyf |
| 阅读次数: | 64 |