NP-completeness of some problems of partitioning and covering in graphs

DOI10.1016/0166-218X(84)90101-XzbMath0541.05048MaRDI QIDQ794673

Bernard Peroche

Publication date: 1984

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

zbMATH Keywords

NP-completepath decompositionsHamilton decompositionspath coverings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (11)

On computing the path number of a graph ⋮ Path covering problems and testing of printed circuits ⋮ Orientation‐based edge‐colorings and linear arboricity of multigraphs ⋮ The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties ⋮ Balancing connected colourings of graphs ⋮ Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Flip distances between graph orientations ⋮ Cycle decompositions and constructive characterizations ⋮ Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph ⋮ Two Hamiltonian cycles

Cites Work

• The Path-Numbers of Some Multipartite Graphs
• Path decompositions of digraphs
• COVERING AND PACKING IN GRAPHS, I.
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: NP-completeness of some problems of partitioning and covering in graphs