Computing Pathwidth Faster Than 2 n
From MaRDI portal
Publication:3656873
DOI10.1007/978-3-642-11269-0_27zbMath1273.68284DBLPconf/iwpec/SuchanV09OpenAlexW2168990208WikidataQ62046054 ScholiaQ62046054MaRDI QIDQ3656873
Publication date: 14 January 2010
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_27
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (11)
On Cutwidth Parameterized by Vertex Cover ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ On cutwidth parameterized by vertex cover ⋮ Computing the pathwidth of directed graphs with small vertex cover ⋮ Computing tree-depth faster than \(2^n\) ⋮ A note on exact algorithms for vertex ordering problems on graphs ⋮ Linear ordering based MIP formulations for the vertex separation or pathwidth problem ⋮ Unnamed Item ⋮ Notes on tree- and path-chromatic number ⋮ Finding small-width connected path decompositions in polynomial time ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
This page was built for publication: Computing Pathwidth Faster Than 2 n