Log-Space Algorithms for Paths and Matchings in k-Trees

Show simple item record

dc.contributor.author Das, Bireswar
dc.contributor.author Datta, Samir
dc.contributor.author Prajakta, Nimbhorkar
dc.date.accessioned 2014-03-17T07:58:23Z
dc.date.available 2014-03-17T07:58:23Z
dc.date.issued 2013-05
dc.identifier.citation Das, Bireswar; Datta, Samir and Prajakta Nimbhorkar, “Log-space algorithms for paths and matchings in k-Trees”, Theory of Computing Systems, DOI: 10.1007/s00224-013-9469-9, vol. 53, no. 4, pp. 669–689, May 2013. en_US
dc.identifier.issn 1432-4350
dc.identifier.issn 1433-0490
dc.identifier.uri http://dx.doi.org/10.1007/s00224-013-9469-9
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/826
dc.description.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, 2007). 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, 2010). 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, 2007) and Limaye et al. (Theory Comput. Syst. 46(3):499–522, 2010). en_US
dc.description.statementofresponsibility by Bireswar Das, Samir Datta and Prajakta Nimbhorkar
dc.format.extent Vol. 53, No. 4, pp. 669–689
dc.language.iso en en_US
dc.publisher Springer Link en_US
dc.subject Log-space en_US
dc.subject Matching en_US
dc.subject Reachability en_US
dc.subject Tree-width en_US
dc.title Log-Space Algorithms for Paths and Matchings in k-Trees en_US
dc.type Article en_US
dc.relation.journal Theory of Computing Systems


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account