Intractability of clique-width parameterizations
From MaRDI portal
Publication:3053155
Recommendations
- Clique-width: on the price of generality
- Algorithmic lower bounds for problems parameterized by clique-width
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
Cited in
(50)- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Efficient parallel algorithms for parameterized problems
- Parameterized complexity for iterated type partitions and modular-width
- Acyclic coloring parameterized by directed clique-width
- Finer tight bounds for coloring on clique-width
- Finer tight bounds for coloring on clique-width
- Spanning trees with few branch vertices in graphs of bounded neighborhood diversity
- A basic parameterized complexity primer
- Clique-width minimization is NP-hard
- Computing the clique-width of cactus graphs
- Computing directed Steiner path covers
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth
- Between treewidth and clique-width
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- Computing the chromatic number using graph decompositions via matrix rank
- Clique-width: on the price of generality
- On the minimum cycle cover problem on graphs with bounded co-degeneracy
- Algorithmic meta-theorems for restrictions of treewidth
- On structural parameterizations of star coloring
- Clique-width is NP-complete
- Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
- scientific article; zbMATH DE number 7764100 (Why is no real title available?)
- \(b\)-coloring parameterized by clique-width
- Digraph coloring and distance to acyclicity
- Fast evaluation of interlace polynomials on graphs of bounded treewidth
- Data reduction for graph coloring problems
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Data reduction for graph coloring problems
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Maximum matching in almost linear time on graphs of bounded clique-width
- Digraph width measures in parameterized algorithmics
- Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
- Approximation algorithms for digraph width parameters
- Algorithmic lower bounds for problems parameterized by clique-width
- Iterated Type Partitions
- On the complexity of some colorful problems parameterized by treewidth
- scientific article; zbMATH DE number 7559420 (Why is no real title available?)
- Clique-width: when hard does not mean impossible
- On the complexity of finding large odd induced subgraphs and odd colorings
- Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
- Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
- Structural parameterizations of clique coloring
- Digraphs of bounded width
- Between treewidth and clique-width
- Latency-bounded target set selection in social networks
- Parameterized complexity of distance labeling and uniform channel assignment problems
- Optimal centrality computations within bounded clique-width graphs
- Induced tree covering and the generalized Yutsis property
- A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
This page was built for publication: Intractability of clique-width parameterizations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3053155)
