Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with pathwidth:
TR12-126 | 23rd September 2012
Shiva Kintali, Sinziana Munteanu

Computing Bounded Path Decompositions in Logspace

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

TR13-113 | 19th August 2013
Moritz Müller, Stefan Szeider

Revisiting Space in Proof Complexity: Treewidth and Pathwidth

So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space. Length-space lower bounds for R(k)-refutations ... more >>>

TR13-162 | 1st October 2013
Janka Chlebíková, Morgan Chopin

The Firefighter Problem: A Structural Analysis

Revisions: 1

We consider the complexity of the firefighter problem where ${b \geq 1}$ firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most three and budget one (Finbow et al. 2007) and on trees of bounded degree $b+3$ for any fixed budget ... more >>>

ISSN 1433-8092 | Imprint