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
- 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
- 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?)
- 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)
- scientific article; zbMATH DE number 1262805 (Why is no real title available?)
- 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
- Graph-Theoretic Concepts in Computer Science
- 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)
