Computing Directed Pathwidth in O(1.89 n ) Time
From MaRDI portal
Publication:4899252
DOI10.1007/978-3-642-33293-7_18zbMath1374.68354OpenAlexW2143561549MaRDI QIDQ4899252
Toshihiro Tano, Keita Komuro, Kenta Kitsunai, Yasuaki Kobayashi, Hisao Tamaki
Publication date: 7 January 2013
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-33293-7_18
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (9)
Computing directed pathwidth in \(O(1.89^n)\) time ⋮ Directed Pathwidth and Palletizers ⋮ Treewidth and pathwidth parameterized by the vertex cover number ⋮ Computing the pathwidth of directed graphs with small vertex cover ⋮ Computing tree-depth faster than \(2^n\) ⋮ Linear ordering based MIP formulations for the vertex separation or pathwidth problem ⋮ Finding small-width connected path decompositions in polynomial time ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth ⋮ On the complexity of the FIFO stack-up problem
This page was built for publication: Computing Directed Pathwidth in O(1.89 n ) Time
