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

DOI10.1016/0166-218X(84)90101-XzbMATH Open0541.05048MaRDI QIDQ794673FDOQ794673

Authors: B. Péroche 

Publication date: 1984

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• COVERING AND PACKING IN GRAPHS, I.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Path-Numbers of Some Multipartite Graphs
• Title not available (Why is that?)
• Path decompositions of digraphs

Cited In (21)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Partitions and well-coveredness: the graph sandwich problem
• Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• Graph theory (algorithmic, algebraic, and metric problems)
• Title not available (Why is that?)
• Cycle decompositions and constructive characterizations
• Title not available (Why is that?)
• 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
• Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
• Path covering problems and testing of printed circuits
• Flip distances between graph orientations
• On computing the path number of a graph
• Two Hamiltonian cycles

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)