Log-space Algorithms for Paths and Matchings in k-trees

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 [JT07]. However, for graphs of tree-width larger than 2, no bound better than NL is known. 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 macthing (decision version), and if so, finding a perfect match- ing (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 [DKR08]. 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 divide-and-conquer approach in log-space, along with some ideas from [JT07] and [LMR07].
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.215-226, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455584
Contributeur : Publications Loria <>
Soumis le : mercredi 10 février 2010 - 16:50:48
Dernière modification le : mercredi 10 février 2010 - 19:47:46
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:01:35

Fichier

das.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455584, version 1

Collections

Citation

Bireswar Das, Samir Datta, Prajakta Nimbhorkar. Log-space Algorithms for Paths and Matchings in k-trees. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.215-226, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455584〉

Partager

Métriques

Consultations de la notice

113

Téléchargements de fichiers

133