Twin-width of graphs with tree-structured decompositions

DOI10.4230/LIPICS.IPEC.2023.25MaRDI QIDQ6926184zbMATH OpenFDO

Authors Irene Heinrich, Simon Raßmann

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2023.25

zbMATH Keywords

quasi-4 connected componentsstrong tree-widthtwin-width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• A short proof of Sperner's lemma
• Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
• Bounds for the twin-width of graphs
• Deciding twin-width at most 4 is NP-complete
• Dividing a Graph into Triconnected Components
• scientific article; zbMATH DE number 3917707 (Why is no real title available?)
• On tree-partition-width
• Quasi-4-Connected Components
• Tree-partitions of infinite graphs
• Twin-width can be exponential in treewidth
• Twin-width of graphs with tree-structured decompositions
• Twin-width. I: Tractable FO model checking
• Twin-width. I: Tractable FO model checking
• Twin-width. VI: The lens of contraction sequences

Cited in

(1)

• Twin-width of graphs with tree-structured decompositions

This page was built for publication: Twin-width of graphs with tree-structured decompositions

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