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)

Full work available at URL https://doi.org/10.1016/0166-218X(84)90101-X

zbMATH Keywords

Hamilton decompositionsNP-completepath coveringspath decompositions

Mathematics Subject Classification ID

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

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

• COVERING AND PACKING IN GRAPHS, I.
• 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?)
• Path decompositions of digraphs
• The Path-Numbers of Some Multipartite Graphs

Cited in

(26)

• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• Path covering problems and testing of printed circuits
• Partitions and well-coveredness: the graph sandwich problem
• Two Hamiltonian cycles
• On computing the path number of a graph
• Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
• The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties
• Balancing connected colourings of graphs
• scientific article; zbMATH DE number 3857154 (Why is no real title available?)
• 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?)
• scientific article; zbMATH DE number 175833 (Why is no real title available?)
• scientific article; zbMATH DE number 5790346 (Why is no real title available?)
• Cycle decompositions and constructive characterizations
• Graph theory (algorithmic, algebraic, and metric problems)
• Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
• Flip distances between graph orientations
• NP-completeness results for partitioning a graph into total dominating sets
• Orientation‐based edge‐colorings and linear arboricity of multigraphs
• Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
• Notes on upper bounds for the largest eigenvalue based on edge-decompositions of a signed graph
• Reachability in graphs having linear 2-arboricity two is \(\mathsf{NL}\)-hard
• The complexity of decomposing a graph into a matching and a bounded linear forest
• On the hardness of short and sign-compatible circuit walks
• Path decompositions of oriented graphs

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)