ECCC-Report TR12-126https://eccc.weizmann.ac.il/report/2012/126Comments and Revisions published for TR12-126en-usTue, 02 Oct 2012 23:51:10 +0200
Paper TR12-126
| Computing Bounded Path Decompositions in Logspace |
Shiva Kintali,
Sinziana Munteanu
https://eccc.weizmann.ac.il/report/2012/126We 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.Tue, 02 Oct 2012 23:51:10 +0200https://eccc.weizmann.ac.il/report/2012/126