Characterizing width two for variants of treewidth

DOI10.1016/j.dam.2015.01.015zbMath1350.05116arXiv1404.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

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

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