The NP-Completeness of Some Edge-Partition Problems
From MaRDI portal
Publication:3922182
DOI10.1137/0210054zbMath0468.68069OpenAlexW2059936808MaRDI QIDQ3922182
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/4f26d96ca5dd7ff2f27810ebca26bd00cddfd52a
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (77)
Edge-disjoint packings of graphs ⋮ On reliable graphs with static routing plans ⋮ A modified greedy heuristic for the set covering problem with improved worst case bound ⋮ The fewest clues problem ⋮ Algorithmic problems in right-angled Artin groups: complexity and applications ⋮ A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing ⋮ Hardness and approximation of traffic grooming ⋮ A column generation approach to job grouping for flexible manufacturing systems ⋮ Clique covering and clique partition in generalizations of line graphs ⋮ Edge-disjoint packing of stars and cycles ⋮ Traffic grooming on the path ⋮ Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial ⋮ Unnamed Item ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Colorful edge decomposition of graphs: some polynomial cases ⋮ Rounding in symmetric matrices and undirected graphs ⋮ Parameterized complexity of \(k\)-Chinese postman problem ⋮ TWO RESULTS ON THE PALETTE INDEX OF GRAPHS ⋮ Edge decompositions and rooted packings of graphs ⋮ Decomposing subcubic graphs into claws, paths or triangles ⋮ Towards a solution of the Holyer's problem ⋮ On graphs with equal coprime index and clique number ⋮ The transposition median problem is NP-complete ⋮ On the complexity and algorithm of grooming regular traffic in WDM optical networks ⋮ Unnamed Item ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ Towards optimal kernel for edge-disjoint triangle packing ⋮ Hardness and Approximation of Traffic Grooming ⋮ Clique partitions of distance multigraphs ⋮ NP-completeness of graph decomposition problems ⋮ On the minimum monochromatic or multicolored subgraph partition problems ⋮ Path multicoloring with fewer colors in spiders and caterpillars ⋮ On the complexity of deciding whether the regular number is at most two ⋮ Approximation algorithms for some min-max postmen cover problems ⋮ Reliable assignments of processors to tasks and factoring on matroids ⋮ The complexity for partitioning graphs by monochromatic trees, cycles and paths ⋮ Packing triangles in low degree graphs and indifference graphs ⋮ Algorithmic complexity of weakly semiregular partitioning and the representation number ⋮ Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees ⋮ On Rooted Packings, Decompositions, and Factors of Graphs ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ Multigraph decomposition into stars and into multistars ⋮ On the fractional chromatic index of a graph and its complement ⋮ Packing disjoint cycles over vertex cuts ⋮ Approximation algorithms for grooming in optical network design ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ How to allocate review tasks for robust ranking ⋮ The edge colorings of \(K_5\)-minor free graphs ⋮ On packing shortest cycles in graphs ⋮ Edge and total coloring of interval graphs ⋮ Unnamed Item ⋮ On the complete width and edge clique cover problems ⋮ Complexity of token swapping and its variants ⋮ Triangle decompositions of planar graphs ⋮ Vertex elimination orderings for hereditary graph classes ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs ⋮ Decomposing Cubic Graphs into Connected Subgraphs of Size Three ⋮ Computational complexity, Newton polytopes, and Schubert polynomials ⋮ Polynomial cases of graph decomposition: A complete solution of Holyer's problem ⋮ Minimum weakly fundamental cycle bases are hard to find ⋮ Approximation algorithms for the design of SDH/SONET networks ⋮ Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps ⋮ On some multigraph decomposition problems and their computational complexity ⋮ Covering the edges of bipartite graphs using \(K_{2,2}\) graphs ⋮ Finding Local Genome Rearrangements ⋮ Edge decompositions into two kinds of graphs ⋮ Embedding partial Steiner triple systems is NP-complete ⋮ Tight Lower Bounds for List Edge Coloring ⋮ The complexity of completing partial Latin squares ⋮ Cycle decompositions and constructive characterizations ⋮ On the complexity of partitioning graphs into connected subgraphs ⋮ Packing triangles in bounded degree graphs. ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Chain packing in graphs ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction ⋮ The complexity of generalized clique packing
This page was built for publication: The NP-Completeness of Some Edge-Partition Problems
