Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
From MaRDI portal
Publication:5173247
Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)
Recommendations
- Algorithmic lower bounds for problems parameterized by clique-width
- On hardness of approximating the parameterized clique problem
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- scientific article; zbMATH DE number 1262783
- Tight complexity bounds for FPT subgraph problems parameterized by clique-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- On the approximability of clique and related maximization problems
- Bounding clique-width via perfect graphs
- Bounding clique-width via perfect graphs
Cited in
(48)- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- Optimal centrality computations within bounded clique-width graphs
- Maximum matching in almost linear time on graphs of bounded clique-width
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Computing the largest bond and the maximum connected cut of a graph
- Integer programming in parameterized complexity: five miniatures
- Tight complexity bounds for FPT subgraph problems parameterized by clique-width
- Sum-of-squares Lower Bounds for Planted Clique
- Between treewidth and clique-width
- Between treewidth and clique-width
- Intractability of clique-width parameterizations
- Clique-width: when hard does not mean impossible
- Digraphs of bounded width
- A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
- Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Known algorithms on graphs of bounded treewidth are probably optimal
- Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- Clique-width: on the price of generality
- Approximating rank-width and clique-width quickly
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Integer programming in parameterized complexity: three miniatures
- More applications of the d-neighbor equivalence: connectivity and acyclicity constraints
- U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Grundy Distinguishes Treewidth from Pathwidth
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- Orthogonal vectors indexing
- A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
- Algorithmic lower bounds for problems parameterized by clique-width
- Grundy distinguishes treewidth from pathwidth
- On the complexity of finding large odd induced subgraphs and odd colorings
- On the minimum cycle cover problem on graphs with bounded co-degeneracy
- Complexity of maximum cut on interval graphs
- Space-efficient parameterized algorithms on graphs of low shrubdepth
- XNLP-completeness for parameterized problems on graphs with a linear structure
- XNLP-completeness for parameterized problems on graphs with a linear structure
- XALP-completeness of parameterized problems on planar graphs
- Equitable connected partition and structural parameters revisited: N-fold beats Lenstra
- Current algorithms for detecting subgraphs of bounded treewidth are probably optimal
- Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
- Bridging treewidth and clique-width via cograph-modular-treewidth
- Quadratic kernel for cliques or trees vertex deletion
This page was built for publication: Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5173247)
