Fixed-parameter tractability and characterizations of small special treewidth

DOI10.1007/978-3-642-45043-3_9zbMATH Open1400.05234OpenAlexW152960333WikidataQ59567506 ScholiaQ59567506MaRDI QIDQ2864293FDOQ2864293

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

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

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

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)

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)