The NP-Completeness of Some Edge-Partition Problems

Cited in

(82)

Polynomial cases of graph decomposition: A complete solution of Holyer's problem
Minimum weakly fundamental cycle bases are hard to find
Covering the edges of bipartite graphs using \(K_{2,2}\) graphs
Edge decompositions into two kinds of graphs
On the complexity of partitioning graphs into connected subgraphs
Combinatorial analysis (nonnegative matrices, algorithmic problems)
The complexity of generalized clique packing
NP-completeness of graph decomposition problems
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
A column generation approach to job grouping for flexible manufacturing systems
Clique covering and clique partition in generalizations of line graphs
Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
The fewest clues problem
Algorithmic problems in right-angled Artin groups: complexity and applications
A (3+)k-vertex kernel for edge-disjoint triangle packing
On some multigraph decomposition problems and their computational complexity
Packing triangles in bounded degree graphs.
Rounding in symmetric matrices and undirected graphs
The edge colorings of \(K_5\)-minor free graphs
Approximation algorithms for some min-max postmen cover problems
Computational complexity, Newton polytopes, and Schubert polynomials
Traffic grooming on the path
Colorful edge decomposition of graphs: some polynomial cases
Towards optimal kernel for edge-disjoint triangle packing
On the minimum monochromatic or multicolored subgraph partition problems
Path multicoloring with fewer colors in spiders and caterpillars
Packing triangles in low degree graphs and indifference graphs
Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
Multigraph decomposition into stars and into multistars
On the fractional chromatic index of a graph and its complement
An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
Vertex elimination orderings for hereditary graph classes
Edge-disjoint packing of stars and cycles
Edge decompositions and rooted packings of graphs
Decomposing cubic graphs into connected subgraphs of size three
Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
Edge-disjoint packing of stars and cycles
Parameterized complexity of \(k\)-Chinese postman problem
On the complexity and algorithm of grooming regular traffic in WDM optical networks
Combinatorial and computational aspects of graph packing and graph decomposition
The complexity for partitioning graphs by monochromatic trees, cycles and paths
Problems and invariants connected with bicliques and multicliques of graphs
On the complexity of deciding whether the regular number is at most two
Cycle decompositions and constructive characterizations
Constrained representations of map graphs and half-squares
Two results on the palette index of graphs
Finding Local Genome Rearrangements
Tight lower bounds for list edge coloring
Algorithmic complexity of weakly semiregular partitioning and the representation number
Hardness and Approximation of Traffic Grooming
On rooted packings, decompositions, and factors of graphs
Approximation algorithms for the design of SDH/SONET networks
Approximation algorithms for grooming in optical network design
Computational Short Cuts in Infinite Domain Constraint Satisfaction
On the Weisfeiler-Leman dimension of fractional packing
Edge and total coloring of interval 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
Partitioning the edge set of a bipartite graph into the minimal number of subgraphs isomorphic to those of a simple 4 order cycle
The transposition median problem is NP-complete
Kernelization for edge triangle packing and covering via a discharging method
A discharging method: improved kernels for edge triangle packing and covering
Reachability of fair allocations via sequential exchanges
Reliable assignments of processors to tasks and factoring on matroids
On the complexity of the median and closest permutation problems
Tetris with few piece types
Packing sets of paths, stars and triangles: tractability and approximability
Better approximating SONET k-edge partition for small capacity k
How to allocate review tasks for robust ranking
Complexity of token swapping and its variants
Triangle decompositions of planar graphs
Embedding partial Steiner triple systems is NP-complete
The complexity of completing partial Latin squares
Chain packing in graphs
Hardness and approximation of traffic grooming
Graph factors and factorization: 1985--2003: a survey
Clique partitions of distance multigraphs
Packing disjoint cycles over vertex cuts
On packing shortest cycles in graphs

This page was built for publication: The NP-Completeness of Some Edge-Partition Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3922182)