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
(65)- Computing the clique-width of cactus graphs
- Algorithmic meta-theorems for restrictions of treewidth
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Optimal centrality computations within bounded clique-width graphs
- Maximum matching in almost linear time on graphs of bounded clique-width
- Computing directed Steiner path covers
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- Efficient parallel algorithms for parameterized problems
- Computing the chromatic number using graph decompositions via matrix rank
- Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
- Parameterized complexity of distance labeling and uniform channel assignment problems
- Digraph width measures in parameterized algorithmics
- Latency-bounded target set selection in social networks
- Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
- A basic parameterized complexity primer
- Clique-width minimization is NP-hard
- Between treewidth and clique-width
- Between treewidth and clique-width
- Data reduction for graph coloring problems
- 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
- Clique-width is NP-complete
- Data reduction for graph coloring problems
- Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- Modular-width: an auxiliary parameter for parameterized parallel complexity
- Clique-width: on the price of generality
- Approximation algorithms for digraph width parameters
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Finer tight bounds for coloring on clique-width
- Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
- Iterated Type Partitions
- scientific article; zbMATH DE number 7559420 (Why is no real title available?)
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Finer tight bounds for coloring on clique-width
- Algorithmic lower bounds for problems parameterized by clique-width
- On the complexity of finding large odd induced subgraphs and odd colorings
- On the minimum cycle cover problem on graphs with bounded co-degeneracy
- scientific article; zbMATH DE number 7764100 (Why is no real title available?)
- Parameterized complexity for iterated type partitions and modular-width
- On structural parameterizations of star coloring
- Spanning trees with few branch vertices in graphs of bounded neighborhood diversity
- On the complexity of some colorful problems parameterized by treewidth
- Fast evaluation of interlace polynomials on graphs of bounded treewidth
- Induced tree covering and the generalized Yutsis property
- Digraph coloring and distance to acyclicity
- \(b\)-coloring parameterized by clique-width
- Making graphs irregular through irregularising walks
- Space-efficient parameterized algorithms on graphs of low shrubdepth
- Sequentially swapping tokens: further on graph classes
- On the complexity of finding a sparse connected spanning subgraph in a non-uniform failure model
- Exact and parameterized algorithms for choosability
- Parameterized complexity of maximum happy set and densest k-subgraph
- XNLP-completeness for parameterized problems on graphs with a linear structure
- On polynomial kernels for traveling salesperson problem and its generalizations
- XNLP-completeness for parameterized problems on graphs with a linear structure
- Induced tree covering and the generalized Yutsis property
- Finding a minimum spanning tree with a small non-terminal set
- Digraph coloring and distance to acyclicity
- b-coloring parameterized by clique-width
- On the parameterized complexity of odd coloring
- Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
- Acyclic coloring parameterized by directed clique-width
- Structural parameterizations of clique coloring
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)
