Between treewidth and clique-width
From MaRDI portal
Publication:300479
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
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