Intractability of clique-width parameterizations
From MaRDI portal
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
(63)- 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
- Exact and parameterized algorithms for choosability
- Induced tree covering and the generalized Yutsis property
- Parameterized complexity of maximum happy set and densest k-subgraph
- XNLP-completeness for parameterized problems on graphs with a linear structure
- Finer tight bounds for coloring on clique-width
- Finer tight bounds for coloring on clique-width
- On polynomial kernels for traveling salesperson problem and its generalizations
- 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
- b-coloring parameterized by clique-width
- Digraph coloring and distance to acyclicity
- XNLP-completeness for parameterized problems on graphs with a linear structure
- 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
- Finding a minimum spanning tree with a small non-terminal set
- 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
- Making graphs irregular through irregularising walks
- Approximation algorithms for digraph width parameters
- Space-efficient parameterized algorithms on graphs of low shrubdepth
- Sequentially swapping tokens: further on graph classes
- 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
- On the complexity of finding a sparse connected spanning subgraph in a non-uniform failure model
- 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)
