scientific article; zbMATH DE number 176762

MaRDI QIDQ4036592zbMATHFDO

Authors Ton Kloks, Hans L. Bodlaender

Publication date 18 May 1993

zbMATH Keywords

algorithmstreewidthpathwidthtree-decompositionpath-decomposition

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• scientific article; zbMATH DE number 566078
• Faster computation of path-width
• An improved algorithm for finding tree decompositions of small width
• scientific article; zbMATH DE number 4173000

Cited in

(35)

• scientific article; zbMATH DE number 7471715 (Why is no real title available?)
• Better \(s-t\)-tours by Gao trees
• Complexity of path-forming games
• Two strikes against perfect phylogeny
• The pathwidth and treewidth of cographs
• Parallel algorithms with optimal speedup for bounded treewidth
• Tree-width and path-width of comparability graphs of interval orders
• Mixed searching and proper-path-width
• Finite integer index of pathwidth and treewidth
• Minor-Closed Graph Classes with Bounded Layered Pathwidth
• Computing Pathwidth Faster Than 2 n
• Kernelization using structural parameters on sparse graph classes
• A simple linear time algorithm for triangulating three-colored graphs
• Approximation algorithms for treewidth
• A lower bound for treewidth and its consequences
• An improved parameterized algorithm for treewidth
• A simple linear-time algorithm for finding path-decompositions of small width
• The Pathwidth and Treewidth of Cographs
• Testing superperfection of k-trees
• Efficient sets in partial \(k\)-trees
• Scheduling with incompatible jobs
• Computing Tree Decompositions
• Approximate tree decompositions of planar graphs in linear time
• Fixed-parameter tractability of treewidth and pathwidth
• Pathwidth of cubic graphs and exact algorithms
• Approximate tree decompositions of planar graphs in linear time
• Peptide sequencing via graph path decomposition
• The complexity of broadcasting in planar and decomposable graphs
• Nondeterministic graph searching: from pathwidth to treewidth
• Fixed-parameter tractability and characterizations of small special treewidth
• A win-win algorithm for the \((k+1)\)-LST/\(k\)-pathwidth problem
• The complexity of broadcasting in planar and decomposable graphs
• scientific article; zbMATH DE number 219268 (Why is no real title available?)
• Treewidth and pathwidth of permutation graphs
• Narrowness, pathwidth, and their application in natural language processing

This page was built for publication:

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