ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-126 | 23rd September 2012 22:29

Computing Bounded Path Decompositions in Logspace

RSS-Feed




TR12-126
Authors: Shiva Kintali, Sinziana Munteanu
Publication: 2nd October 2012 23:51
Downloads: 1643
Keywords: 


Abstract:

We present a logspace algorithm to compute path decompositions of bounded pathwidth graphs, thus settling its complexity. Prior to our work, the best known upper bound to compute such decompositions was linear time. We also show that deciding if the pathwidth of a graph is at most a given constant is L-complete. Besides being of fundamental interest, our results represent an important step to gain a better understanding of the complexity of Graph Isomorphism of bounded pathwidth graphs.



ISSN 1433-8092 | Imprint