Between Treewidth and Clique-Width

DOI10.1007/978-3-319-12340-0_33zbMath1409.05201arXiv1404.7758OpenAlexW2125561319MaRDI QIDQ2945207

Sigve Hortemo Sæther, Jan Arne Telle

Publication date: 9 September 2015

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

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

zbMATH Keywords

graph coloringHamiltonian cycleMaxCutedge dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45)

Related Items (7)

Between Treewidth and Clique-Width ⋮ Maximum matching width: new characterizations and a fast algorithm for dominating set ⋮ Structural parameterizations of budgeted graph coloring ⋮ Parameterized Compilation Lower Bounds for Restricted CNF-Formulas ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ Unnamed Item ⋮ Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter

Cites Work

• Unnamed Item
• Boolean-width of graphs
• Solving some NP-complete problems using split decomposition
• Graph minors. X: Obstructions to tree-decomposition
• Algorithmic meta-theorems for restrictions of treewidth
• Linear time solvable optimization problems on graphs of bounded clique-width
• Approximating clique-width and branch-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Parameterized Algorithms for Modular-Width
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Linear Time Split Decomposition Revisited
• When Trees Grow Low: Shrubs and Fast MSO1
• Between Treewidth and Clique-Width
• Decomposition of Directed Graphs
• On the Relationship Between Clique-Width and Treewidth

This page was built for publication: Between Treewidth and Clique-Width