How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
From MaRDI portal
Recommendations
- Computing Graph Polynomials on Graphs of Bounded Clique-Width
- Linear time solvable optimization problems on graphs of bounded clique width
- Linear time solvable optimization problems on graphs of bounded clique-width
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- scientific article; zbMATH DE number 6850484
- Clique-width is NP-complete
- Algorithmic lower bounds for problems parameterized by clique-width
- On graphs with polynomially solvable maximum-weight clique problem
- Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)
- Clique-width minimization is NP-hard
Cited in
(72)- Query efficient implementation of graphs of bounded clique-width
- On \textsf{NC} algorithms for problems on bounded rank-width graphs
- Oriented coloring on recursively defined digraphs
- Optimal centrality computations within bounded clique-width graphs
- Maximum matching in almost linear time on graphs of bounded clique-width
- Minimum maximal matchings in cubic graphs
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
- Comparing linear width parameters for directed graphs
- Colouring square-free graphs without long induced paths
- Knocking out \(P_k\)-free graphs
- Polynomial algorithms for protein similarity search for restricted mRNA structures
- On powers of graphs of bounded NLC-width (clique-width)
- Colouring diamond-free graphs
- Obstructions for linear rank-width at most 1
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- Line graphs of bounded clique-width
- Approximating clique-width and branch-width
- Vertex disjoint paths on clique-width bounded graphs
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- Computing maximum stable sets for distance-hereditary graphs
- On the relationship between NLC-width and linear NLC-width
- Well-quasi-ordering versus clique-width: new results on bigenic classes
- 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
- Graphs of separability at most two: structural characterizations and their consequences
- Digraphs of bounded width
- scientific article; zbMATH DE number 992954 (Why is no real title available?)
- Colouring square-free graphs without long induced paths
- A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
- On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
- Computing Graph Polynomials on Graphs of Bounded Clique-Width
- Clique-width is NP-complete
- Graphs of separability at most 2
- Polynomial-time recognition of clique-width 3 graphs
- On switching classes, NLC-width, cliquewidth and treewidth
- scientific article; zbMATH DE number 6850484 (Why is no real title available?)
- scientific article; zbMATH DE number 7029306 (Why is no real title available?)
- On the parameterized complexity of computing balanced partitions in graphs
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Tree pivot-minors and linear rank-width
- scientific article; zbMATH DE number 7204407 (Why is no real title available?)
- Clique-width for graph classes closed under complementation
- The behavior of clique-width under graph operations and graph transformations
- Covering a graph with clubs
- Canonisation and Definability for Graphs of Bounded Rank Width
- Clique-width and well-quasi-ordering of triangle-free graph classes
- Fair allocation algorithms for indivisible items under structured conflict constraints
- Clique‐width: Harnessing the power of atoms
- Stability, vertex stability, and unfrozenness for special graph classes
- Succinct data structures for bounded clique-width graphs
- \(b\)-coloring parameterized by clique-width
- A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
- Word-representable graphs and locality of words
- Atoms versus avoiding simplicial vertices
- Well-quasi-ordering versus clique-width: new results on bigenic classes
- b-coloring parameterized by clique-width
- Tight bounds for connected odd cycle transversal parameterized by clique-width
- A graph width perspective on partially ordered Hamiltonian paths and cycles ii: vertex and edge deletion numbers
- On algorithms for (P₅, gem)-free graphs
- Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
- Acyclic coloring parameterized by directed clique-width
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Characterizations for restricted graphs of NLC-width 2
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Directed NLC-width
- Solving some NP-complete problems using split decomposition
- Recent developments on graphs of bounded clique-width
- \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
This page was built for publication: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4448752)
