Fixed-parameter tractability and characterizations of small special treewidth

DOI10.1007/978-3-642-45043-3_9MaRDI QIDQ2864293zbMATH OpenOpenAlexWikidataFDO

Authors Stefan Kratsch, Vincent J. C. Kreuzen, Hans L. Bodlaender

Publication date 6 December 2013

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45043-3_9

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Recommendations

• Characterizing width two for variants of treewidth
• Fixed-parameter tractability of treewidth and pathwidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• scientific article; zbMATH DE number 219268
• scientific article; zbMATH DE number 176762

Cited in

(4)

• From tree-decompositions to clique-width terms
• Characterizing width two for variants of treewidth
• Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach

This page was built for publication: Fixed-parameter tractability and characterizations of small special treewidth

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