Between treewidth and clique-width

DOI10.1007/s00453-015-0033-7zbMath1345.05104MaRDI QIDQ300479

Jan Arne Telle, Sigve Hortemo Sæther

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 algorithms; split decompositions; width parameters of graphs

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Unnamed Item, Finer Tight Bounds for Coloring on Clique-Width, Computing the Chromatic Number Using Graph Decompositions via Matrix Rank, Measuring what matters: a hybrid approach to dynamic programming with treewidth, Computing the chromatic number using graph decompositions via matrix rank, Characterizing graphs of maximum matching width at most 2, On Structural Parameterizations of Graph Motif and Chromatic Number

Cites Work

• Unnamed Item
• Boolean-width of graphs
• Solving some NP-complete problems using split decomposition
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• 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
• Rank-width and vertex-minors
• 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
• Intractability of Clique-Width Parameterizations
• Decomposition of Directed Graphs
• Solving Hamiltonian Cycle by an EPT Algorithm for a Non-sparse Parameter
• On the Relationship Between Clique-Width and Treewidth
• Directed Nowhere Dense Classes of Graphs