Solving some NP-complete problems using split decomposition
From MaRDI portal
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Recommendations
Cites work
- 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 2044928 (Why is no real title available?)
- scientific article; zbMATH DE number 1496855 (Why is no real title available?)
- scientific article; zbMATH DE number 1456953 (Why is no real title available?)
- 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
- 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
(17)- 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
- SPLITTING NUMBER is NP-complete
- Solving larger maximum clique problems using parallel quantum annealing
- The \(b\)-\textsc{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
- Between treewidth and clique-width
- Graph-Theoretic Concepts in Computer Science
- Word-representability of graphs with respect to split recomposition
- Using split composition to extend distance-hereditary graphs in a generative way (extended abstract)
- Maximum matching in almost linear time on graphs of bounded clique-width
- scientific article; zbMATH DE number 7561384 (Why is no real title available?)
- Grammars and clique-width bounds from split decompositions
- Parameterized algorithms for the independent set problem in some hereditary graph classes
- scientific article; zbMATH DE number 1262805 (Why is no real title available?)
- Between treewidth and clique-width
- Distance-hereditary comparability graphs
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)
