Back to Search
Start Over
Log-Space Algorithms for Paths and Matchings in k-Trees.
- Source :
- Theory of Computing Systems; Nov2013, Vol. 53 Issue 4, p669-689, 21p, 3 Diagrams
- Publication Year :
- 2013
-
Abstract
- Reachability and shortest path problems are NL-complete for general graphs. They are known to be in L for graphs of tree-width 2 (Jakoby and Tantau in Proceedings of FSTTCS'07: The 27th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 216-227, ). In this paper, we improve these bounds for k-trees, where k is a constant. In particular, the main results of our paper are log-space algorithms for reachability in directed k-trees, and for computation of shortest and longest paths in directed acyclic k-trees. Besides the path problems mentioned above, we also consider the problem of deciding whether a k-tree has a perfect matching (decision version), and if so, finding a perfect matching (search version), and prove that these two problems are L-complete. These problems are known to be in P and in RNC for general graphs, and in SPL for planar bipartite graphs, as shown in Datta et al. (Theory Comput. Syst. 47:737-757, ). Our results settle the complexity of these problems for the class of k-trees. The results are also applicable for bounded tree-width graphs, when a tree-decomposition is given as input. The technique central to our algorithms is a careful implementation of the divide-and-conquer approach in log-space, along with some ideas from Jakoby and Tantau (Proceedings of FSTTCS'07: The 27th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 216-227, ) and Limaye et al. (Theory Comput. Syst. 46(3):499-522, ). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 53
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 89547444
- Full Text :
- https://doi.org/10.1007/s00224-013-9469-9