Solving some NP-complete problems using split decomposition
From MaRDI portal
Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
Cites work
- A new linear algorithm for modular decomposition
- An O(n2) Algorithm for Undirected Split Decomposition
- Completely separable graphs
- Computing the treewidth and the minimum fill-in with the modular decomposition
- Decomposition by clique separators
- Decomposition of Directed Graphs
- Easy problems for tree-decomposable graphs
- Edge dominating set and colorings on graphs with fixed clique-width
- Handle-rewriting hypergraph grammars
- How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 3887730 (Why is no real title available?)
- scientific article; zbMATH DE number 3906240 (Why is no real title available?)
- scientific article; zbMATH DE number 1496855 (Why is no real title available?)
- Linear time solvable optimization problems on graphs of bounded clique-width
- Modular decomposition and transitive orientation
- On algorithms for (P₅, gem)-free graphs
- On the extension of bipartite to parity graphs
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- Recognition of Circle Graphs
- Recognizing circle graphs in polynomial time
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- The strong perfect graph theorem
- Upper bounds to the clique width of graphs
Cited in
(18)- Distance-hereditary comparability graphs
- Maximum matching in almost linear time on graphs of bounded clique-width
- Grammars and clique-width bounds from split decompositions
- The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
- Between treewidth and clique-width
- Parameterized algorithms for the independent set problem in some hereditary graph classes
- Between treewidth and clique-width
- Using split composition to extend distance-hereditary graphs in a generative way (extended abstract)
- Splitting number is NP-complete
- Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- The \(b\)-matching problem in distance-hereditary graphs and beyond
- All NP-Problems Can Be Solved in Polynomial Time by Accepting Networks of Splicing Processors of Constant Size
- Coloring a graph using split decomposition
- SPLITTING NUMBER is NP-complete
- Solving larger maximum clique problems using parallel quantum annealing
- Word-representability of graphs with respect to split recomposition
- A canonical tree decomposition for order types, and some applications
This page was built for publication: Solving some NP-complete problems using split decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q948695)