On the complexity of some edge-partition problems for graphs

DOI10.1016/0166-218X(95)00107-3zbMath0860.05061MaRDI QIDQ1923590

Zbigniew Lonc

Publication date: 9 October 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

complexitypartitiondecompositioncharacterizationlinear time algorithmNP-complete

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (8)

Improved Approximation Algorithms for Weighted 2-Path Partitions ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Edge decompositions and rooted packings of graphs ⋮ Exact algorithms for finding longest cycles in claw-free graphs ⋮ Improved approximation algorithms for weighted 2-path partitions ⋮ On the complexity of deciding whether the regular number is at most two ⋮ Chain partitions of ordered sets ⋮ Edge decompositions into two kinds of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Packings by cliques and by finite families of graphs
• Packing subgraphs in a graph
• NP-completeness of graph decomposition problems
• Edge-disjoint packings of graphs
• On the Complexity of General Graph Factor Problems
• Packings by Complete Bipartite Graphs
• Graphs with 1-Factors

This page was built for publication: On the complexity of some edge-partition problems for graphs