NP-completeness of graph decomposition problems
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3974987 (Why is no real title available?)
- scientific article; zbMATH DE number 3710196 (Why is no real title available?)
- scientific article; zbMATH DE number 3517174 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 3K2-decomposition of a graph
- A note on the decomposition of graphs into isomorphic matchings
- On the completeness of a generalized matching problem
- The NP-Completeness of Some Edge-Partition Problems
Cited in
(36)- Edge exchanges in Hamiltonian decompositions of Kronecker-product graphs
- Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube
- Clique and anticlique partitions of graphs
- Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
- On the complexity of some edge-partition problems for graphs
- On rooted packings, decompositions, and factors of graphs
- Scheduling jobs on identical machines with agreement graph
- Edge decompositions into two kinds of graphs
- Algorithmic problems in right-angled Artin groups: complexity and applications
- Mutual exclusion scheduling with interval graphs or related classes. II
- Clique and anticlique partitions of graphs
- Delta-system decompositions of graphs
- Input-output decomposition of dynamic systems is NP-complete
- Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
- Polynomial cases of graph decomposition: A complete solution of Holyer's problem
- Trahtenbrot-Zykov problem and NP-completeness
- Edge-disjoint packings of graphs
- The mutual exclusion scheduling problem for permutation and comparability graphs.
- Decomposition of large combinatorial structures
- On some multigraph decomposition problems and their computational complexity
- Clique partitioning with value-monotone submodular cost
- Graph decomposition of slim graphs
- Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints
- Edge decompositions and rooted packings of graphs
- Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
- A Helly property of arcs
- Equitable colorings of bounded treewidth graphs
- scientific article; zbMATH DE number 1472110 (Why is no real title available?)
- Mutual exclusion scheduling with interval graphs or related classes. I
- Towards a solution of the Holyer's problem
- On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem
- Graphs having the local decomposition property
- Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints
- Multigraph decomposition into stars and into multistars
- Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
- scientific article; zbMATH DE number 4101253 (Why is no real title available?)
This page was built for publication: NP-completeness of graph decomposition problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1179032)
