A simple linear-time algorithm for finding path-decompositions of small width

DOI10.1016/0020-0190(95)00190-5zbMath0875.68699arXivmath/9410211OpenAlexW2060966063WikidataQ57360096 ScholiaQ57360096MaRDI QIDQ672094

Michael R. Fellows, Michael J. Dinneen, Kevin Cattell

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

AlgorithmsAnalysis of algorithmsCombinatorial problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Unnamed Item, Approximating Pathwidth for Graphs of Small Treewidth, Convergence of Newton's method over commutative semirings, Minor-Closed Graph Classes with Bounded Layered Pathwidth, A partial k-arboretum of graphs with bounded treewidth, On computing graph minor obstruction sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monadic second-order evaluations on tree-decomposable graphs
• Graph minors. XX: Wagner's conjecture
• Graph minors. I. Excluding a forest
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Graph minors. X: Obstructions to tree-decomposition
• Quickly excluding a forest
• The vertex separation and search number of a graph
• Graph minors. XIII: The disjoint paths problem
• Graph minors. II. Algorithmic aspects of tree-width
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Obstructions to within a few vertices or edges of acyclic
• A linear time algorithm for finding tree-decompositions of small treewidth