Clique-width: on the price of generality
From MaRDI portal
Publication:4633895
zbMATH Open1421.68125MaRDI QIDQ4633895FDOQ4633895
Authors: Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh 
Publication date: 6 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=1496860
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (39)
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- Efficient parallel algorithms for parameterized problems
- Directed NLC-width
- On the Relationship Between Clique-Width and Treewidth
- On the computational difficulty of the terminal connection problem
- Spanning trees with few branch vertices in graphs of bounded neighborhood diversity
- Clique-width minimization is NP-hard
- Algorithmic applications of tree-cut width
- \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
- Recent developments on graphs of bounded clique-width
- An extension of the bivariate chromatic polynomial
- Planar capacitated dominating set is \(W[1]\)-hard
- Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth
- Title not available (Why is that?)
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Oriented coloring on recursively defined digraphs
- Between treewidth and clique-width
- On the minimum cycle cover problem on graphs with bounded co-degeneracy
- Clique-width is NP-complete
- Tight complexity bounds for FPT subgraph problems parameterized by clique-width
- Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
- New graph classes of bounded clique-width
- Methods for determining cycles of a specific length in undirected graphs with edge weights
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Confronting intractability via parameters
- On digraph width measures in parameterized algorithmics
- Critical properties of graphs of bounded clique-width
- Intractability of clique-width parameterizations
- Algorithmic lower bounds for problems parameterized by clique-width
- Iterated Type Partitions
- Optimizing concurrency under Scheduling by Edge Reversal
- Clique-width: when hard does not mean impossible
- Multi-clique-width
- Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)
- Between treewidth and clique-width
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Parameterized complexity for iterated type partitions and modular-width
This page was built for publication: Clique-width: on the price of generality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4633895)
