Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
复制标题
用于计算串并联图中最短和最长路径的对数空间算法
DOI：
10.1007/978-3-540-77050-3_18
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Till Tantau
中科院分区：
文献类型：
--
作者：
A. Jakoby;Till Tantau
对于许多类型的图，包括有向无环图、无向图、锦标赛图和有界独立数图，最短路径问题是NL完全的。对于许多类型的图来说，最长路径问题甚至是 NP 完全的，包括无向 K5-minor-free 图和平面图。在本文中，我们提出了用于计算串并图中的最短和最长路径的对数空间算法，其中边可以任意定向。我们研究的串并联图类可以被表征为 K4-minor-free 图类，也可以被表征为树宽 2 的图类。众所周知，对于有界树宽图，可以有效地解决许多棘手的问题，但以前的工作主要集中在寻找具有低并行或顺序时间复杂度的算法。相反，我们的结果涉及最短和最长路径问题的空间复杂度。特别是，我们的结果表明，对于树宽为 2 的有向图，这些问题是 L 完全的。
For many types of graphs, including directed acyclic graphs, undirected graphs, tournament graphs, and graphs with bounded independence number, the shortest path problem is NL-complete. The longest path problem is even NP-complete for many types of graphs, including undirectedK5-minor-free graphs and planar graphs. In the present paper we present logspace algorithms for computing shortest and longest paths in series-parallel graphs where the edges can be directed arbitrarily. The class of series-parallel graphs that we study can be characterized alternatively as the class ofK4-minor-free graphs and also as the class of graphs of tree-width 2. It is well-known that for graphs of bounded tree-width many intractable problems can be solved efficiently, but previous work was focused on finding algorithms with low parallel or sequentialtime complexity. In contrast, our results concern thespace complexityof shortest and longest path problems. In particular, our results imply that for directed graphs of tree-width 2 these problems are L-complete.