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

DOI10.1016/0166-218X(84)90101-XMaRDI QIDQ794673zbMATH OpenFDO

Authors B. Péroche

Publication date 1984

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

zbMATH Keywords

NP-completepath decompositionsHamilton decompositionspath coverings

Mathematics Subject Classification ID

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

Recommendations

• The path partition problem and related problems in bipartite graphs
• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• scientific article; zbMATH DE number 3857154
• NP-completeness of some edge-disjoint paths problems
• Bipartite spanning sub(di)graphs induced by 2-partitions

Cites work

• scientific article; zbMATH DE number 3674122 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3428965 (Why is no real title available?)
• scientific article; zbMATH DE number 3353324 (Why is no real title available?)
• scientific article; zbMATH DE number 3404271 (Why is no real title available?)
• COVERING AND PACKING IN GRAPHS, I.
• Path decompositions of digraphs
• The Path-Numbers of Some Multipartite Graphs

Cited in

(21)

• Partitions and well-coveredness: the graph sandwich problem
• Two Hamiltonian cycles
• Graph theory (algorithmic, algebraic, and metric problems)
• Orientation‐based edge‐colorings and linear arboricity of multigraphs
• The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• scientific article; zbMATH DE number 3857154 (Why is no real title available?)
• Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
• Recouvrement et partition en chaînes des arêtes d'un graphe cubique
• scientific article; zbMATH DE number 4080906 (Why is no real title available?)
• Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
• Cycle decompositions and constructive characterizations
• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• Flip distances between graph orientations
• On computing the path number of a graph
• Path covering problems and testing of printed circuits
• scientific article; zbMATH DE number 175833 (Why is no real title available?)
• Balancing connected colourings of graphs
• scientific article; zbMATH DE number 5790346 (Why is no real title available?)
• NP-completeness results for partitioning a graph into total dominating sets
• Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming

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

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