All reports by Author Sinziana Munteanu:

__
TR12-126
| 23rd September 2012
__

Shiva Kintali, Sinziana Munteanu#### Computing Bounded Path Decompositions in Logspace

Shiva Kintali, Sinziana Munteanu

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 ... more >>>