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

DOI10.1016/0020-0190(95)00190-5MaRDI QIDQ672094zbMATH OpenOpenAlexDBLPWikidataFDO

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

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

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

Abstract: We described a simple algorithm running in linear time for each fixed constant $k$, that either establishes that the pathwidth of a graph $G$ is greater than $k$, or finds a path-decomposition of $G$ of width at most $O(2^k)$. This provides a simple proof of the result by Bodlaender that many families of graphs of bounded pathwidth can be recognized in linear time.

Recommendations

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• scientific article; zbMATH DE number 4173000
• An improved algorithm for finding tree decompositions of small width
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• scientific article; zbMATH DE number 176762

Cites work

• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• scientific article; zbMATH DE number 3974289 (Why is no real title available?)
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 176762 (Why is no real title available?)
• scientific article; zbMATH DE number 1354123 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1554933 (Why is no real title available?)
• scientific article; zbMATH DE number 4121424 (Why is no real title available?)
• A linear time algorithm for finding tree-decompositions of small treewidth
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Monadic second-order evaluations on tree-decomposable graphs
• Obstructions to within a few vertices or edges of acyclic
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Quickly excluding a forest
• The vertex separation and search number of a graph

Cited in

(12)

• Approximating Pathwidth for Graphs of Small Treewidth
• From edge decomposition formulae to composition algorithms
• On computing graph minor obstruction sets
• A partial k-arboretum of graphs with bounded treewidth
• Minor-Closed Graph Classes with Bounded Layered Pathwidth
• Convergence of Newton's method over commutative semirings
• scientific article; zbMATH DE number 1420905 (Why is no real title available?)
• A linear-time parameterized algorithm for computing the width of a DAG
• scientific article; zbMATH DE number 4173000 (Why is no real title available?)
• Computing Resolution-Path Dependencies in Linear Time ,
• Finding small separators in linear time via treewidth reduction
• Algorithms for solving problems on graphs of bounded pathwidth

This page was built for publication: A simple linear-time algorithm for finding path-decompositions of small width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672094)