NP-completeness of graph decomposition problems
From MaRDI portal
Publication:1179032
DOI10.1016/0885-064X(91)90006-JzbMath0741.68055OpenAlexW2066714987MaRDI QIDQ1179032
Publication date: 26 June 1992
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0885-064x(91)90006-j
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (28)
Edge-disjoint packings of graphs ⋮ Algorithmic problems in right-angled Artin groups: complexity and applications ⋮ Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial ⋮ Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Delta-system decompositions of graphs ⋮ Decomposition of large combinatorial structures ⋮ A Helly property of arcs ⋮ Edge exchanges in Hamiltonian decompositions of Kronecker-product graphs ⋮ On the complexity of some edge-partition problems for graphs ⋮ Edge decompositions and rooted packings of graphs ⋮ Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ The mutual exclusion scheduling problem for permutation and comparability graphs. ⋮ Towards a solution of the Holyer's problem ⋮ Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube ⋮ On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem ⋮ Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem ⋮ Mutual exclusion scheduling with interval graphs or related classes. II ⋮ Star Partitions of Perfect Graphs ⋮ On Rooted Packings, Decompositions, and Factors of Graphs ⋮ Scheduling jobs on identical machines with agreement graph ⋮ Multigraph decomposition into stars and into multistars ⋮ Mutual exclusion scheduling with interval graphs or related classes. I ⋮ Polynomial cases of graph decomposition: A complete solution of Holyer's problem ⋮ On some multigraph decomposition problems and their computational complexity ⋮ Edge decompositions into two kinds of graphs ⋮ Clique and anticlique partitions of graphs ⋮ Clique partitioning with value-monotone submodular cost ⋮ Equitable colorings of bounded treewidth graphs
Cites Work
This page was built for publication: NP-completeness of graph decomposition problems
