scientific article; zbMATH DE number 176762

MaRDI QIDQ4036592zbMATH OpenFDO

Authors Ton Kloks, Hans L. Bodlaender

Publication date 18 May 1993

zbMATH Keywords

algorithmspath-decompositionpathwidthtree-decompositiontreewidth

Mathematics Subject Classification ID

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

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

(38)

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

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)