Between treewidth and clique-width

DOI10.1007/S00453-015-0033-7MaRDI QIDQ300479zbMATH OpenOpenAlexFDO

Authors Sigve Hortemo Sæther, Jan Arne Telle

Publication date 28 June 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-015-0033-7

zbMATH Keywords

parameterized algorithmssplit decompositionswidth parameters of graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Between treewidth and clique-width
• Clique-width: on the price of generality
• Algorithmic lower bounds for problems parameterized by clique-width
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• On the Relationship Between Clique-Width and Treewidth

Cites work

• Algorithmic lower bounds for problems parameterized by clique-width
• Algorithmic meta-theorems for restrictions of treewidth
• Approximating clique-width and branch-width
• Boolean-width of graphs
• Decomposition of Directed Graphs
• Directed Nowhere Dense Classes of Graphs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. X: Obstructions to tree-decomposition
• Intractability of clique-width parameterizations
• Linear time solvable optimization problems on graphs of bounded clique-width
• Linear time split decomposition revisited
• On the Relationship Between Clique-Width and Treewidth
• Parameterized Algorithms for Modular-Width
• Rank-width and vertex-minors
• Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
• Solving some NP-complete problems using split decomposition
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)

Cited in

(13)

• Finer tight bounds for coloring on clique-width
• Finer tight bounds for coloring on clique-width
• On structural parameterizations of graph motif and chromatic number
• Computing the chromatic number using graph decompositions via matrix rank
• Clique-width: on the price of generality
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Edge-treewidth: algorithmic and combinatorial properties
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Characterizing graphs of maximum matching width at most 2
• Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
• Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
• Between treewidth and clique-width

This page was built for publication: Between treewidth and clique-width

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