Faster Computation of Path-Width

DOI10.1007/978-3-319-44543-4_30zbMath1478.68238arXiv1606.06566OpenAlexW2963904830MaRDI QIDQ2819521

Martin Fuerer

Publication date: 29 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.06566

zbMATH Keywords

path decompositiontree-widthpath-widthFPTBodlaender's algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10)

Related Items

FPT algorithms to enumerate and count acyclic and totally cyclic orientations, A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth, A faster parameterized algorithm for pseudoforest deletion, Unnamed Item, Typical sequences revisited -- computing width parameters of graphs, Cutwidth: obstructions and algorithmic aspects, Linear ordering based MIP formulations for the vertex separation or pathwidth problem, Finding small-width connected path decompositions in polynomial time

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Graph minors. XIII: The disjoint paths problem
• Parametrized complexity theory.
• Tree-depth, subgraph coloring and homomorphism bounds
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A Faster Parameterized Algorithm for Treedepth
• AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth