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)

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

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)