Characterizing width two for variants of treewidth

DOI10.1016/j.dam.2015.01.015zbMath1350.05116DBLPjournals/dam/BodlaenderKKKO17arXiv1404.3155OpenAlexW2084535634WikidataQ59567366 ScholiaQ59567366MaRDI QIDQ344827

O-joung Kwon, Vincent J. C. Kreuzen, Stefan Kratsch, Hans L. Bodlaender, Seongmin Ok

Publication date: 24 November 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1404.3155

zbMATH Keywords

minortreewidthspaghetti treewidthspecial treewidthstrongly chordal treewidth

Mathematics Subject Classification ID

Related Items (3)

Characterizing graphs of maximum matching width at most 2 ⋮ From tree-decompositions to clique-width terms ⋮ Finding cut-vertices in the square roots of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Forbidden graphs for tree-depth
• On the model-checking of monadic second-order formulas with edge set quantifications
• Graph minors. XX: Wagner's conjecture
• Forbidden minors characterization of partial 3-trees
• Nondeterministic graph searching: from pathwidth to treewidth
• Characterizations of strongly chordal graphs
• Graph minors. I. Excluding a forest
• Edge and vertex intersection of paths in a tree
• Intersection graphs of paths in a tree
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• A recognition algorithm for the intersection graphs of paths in trees
• A partial k-arboretum of graphs with bounded treewidth
• The forbidden subgraph characterization of directed vertex graphs
• The vertex separation and search number of a graph
• Obstruction set isolation for the gate matrix layout problem
• Treewidth. Computations and approximations
• Neighborhood subtree tolerance graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Fixed-Parameter Tractability and Characterizations of Small Special Treewidth
• On the structure of graphs with path-width at most two
• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• A characterization of partial 3-trees
• Graph minors. II. Algorithmic aspects of tree-width
• Graph Classes: A Survey
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Rankings of Graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• On intervalizing \(k\)-colored graphs for DNA physical mapping

This page was built for publication: Characterizing width two for variants of treewidth