Clique-width is NP-complete
From MaRDI portal
Recommendations
Cited in
(67)- Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
- Automata for the verification of monadic second-order graph properties
- Alliances in graphs of bounded clique-width
- \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- Optimal centrality computations within bounded clique-width graphs
- Grammars and clique-width bounds from split decompositions
- On quasi-planar graphs: clique-width and logical description
- Between clique-width and linear clique-width of bipartite graphs
- Comparing linear width parameters for directed graphs
- Clique-width of full bubble model graphs
- Linear rank-width and linear clique-width of trees
- A characterisation of clique-width through nested partitions
- The rank-width of edge-coloured graphs
- From tree-decompositions to clique-width terms
- Bounding clique-width via perfect graphs
- The relative clique-width of a graph
- Clique-width of path powers
- Bounding clique-width via perfect graphs
- Tight complexity bounds for FPT subgraph problems parameterized by clique-width
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- A basic parameterized complexity primer
- Clique-width minimization is NP-hard
- Bounding the clique-width of H-free chordal graphs
- Clique-width of graph classes defined by two forbidden induced subgraphs
- Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Polynomial-time recognition of clique-width 3 graphs
- On the model-checking of monadic second-order formulas with edge set quantifications
- Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
- scientific article; zbMATH DE number 2044928 (Why is no real title available?)
- Clique-width with an inactive label
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Complexity of conflict-free colorings of graphs
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Finer tight bounds for coloring on clique-width
- Neighbourhood-width of trees
- Finding branch-decompositions of matroids, hypergraphs, and more
- Iterated Type Partitions
- U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- scientific article; zbMATH DE number 7204407 (Why is no real title available?)
- Clique-width for graph classes closed under complementation
- Finer tight bounds for coloring on clique-width
- The behavior of clique-width under graph operations and graph transformations
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Letter graphs and geometric grid classes of permutations: characterization and recognition
- Computations by fly-automata beyond monadic second-order logic
- On the computational difficulty of the terminal connection problem
- Fair allocation algorithms for indivisible items under structured conflict constraints
- Stability, vertex stability, and unfrozenness for special graph classes
- Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs
- Succinct data structures for bounded clique-width graphs
- Fast FPT-approximation of branchwidth
- Hardness of monadic second-order formulae over succinct graphs
- A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
- On using SAT solvers for graph computations
- Word-representable graphs and locality of words
- Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
- Graphs of linear clique-width at most 3
- Structural parameters for dense temporal graphs
- \(\mathcal{H}\)-clique-width and a hereditary analogue of product structure
- Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
- Parameterized spanning tree congestion
- Twin-width. VIIIa: Delineation
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Graph classes with and without powers of bounded clique-width
- Directed NLC-width
This page was built for publication: Clique-width is NP-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3563951)
