Clique-width minimization is NP-hard
DOI10.1145/1132516.1132568zbMATH Open1301.68145OpenAlexW2019880676WikidataQ130980217 ScholiaQ130980217MaRDI QIDQ2931399FDOQ2931399
Authors: Michael R. Fellows, Frances Rosamond, Stefan Szeider, Udi Rotics 
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1132516.1132568
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cited In (28)
- Title not available (Why is that?)
- A new representation of proper interval graphs with an application to clique-width
- Minimal classes of graphs of unbounded clique-width
- Mike Fellows: Weaving the Web of Mathematics and Adventure
- A basic parameterized complexity primer
- Title not available (Why is that?)
- On a disparity between relative cliquewidth and relative NLC-width
- Recent developments on graphs of bounded clique-width
- Constrained-path labellings on graphs of bounded clique-width
- Eigenvalue location in graphs of small clique-width
- New Plain-Exponential Time Classes for Graph Homomorphism
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Clique-width is NP-complete
- Title not available (Why is that?)
- Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width
- Line graphs of bounded clique-width
- Graph operations characterizing rank-width
- Locating Eigenvalues of Symmetric Matrices - A Survey
- The relative clique-width of a graph
- Inductive computations on graphs defined by clique-width expressions
- New plain-exponential time classes for graph homomorphism
- \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
- Graphs of Linear Clique-Width at Most 3
- Vertex-minor reductions can simulate edge contractions
- Graph parameters measuring neighbourhoods in graphs-bounds and applications
- Polynomial algorithms for protein similarity search for restricted mRNA structures
- Pathwidth is NP-Hard for Weighted Trees
This page was built for publication: Clique-width minimization is NP-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931399)
