On the complexity of partitioning graphs into connected subgraphs

DOI10.1016/0166-218X(85)90008-3zbMath0562.68030WikidataQ56324173 ScholiaQ56324173MaRDI QIDQ1057062

Martin Dyer, Alan M. Frieze

Publication date: 1985

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

zbMATH Keywords

NP-completeness; planar bipartite graphs; k-partition of a graph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05A17: Combinatorial aspects of partitions of integers

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C40: Connectivity

Related Items

PARTITIONING TREES OF SUPPLY AND DEMAND, Unnamed Item, Unnamed Item, Max-min weight balanced connected partition, A plane graph representation of triconnected graphs, A linear algorithm for bipartition of biconnected graphs, Bicolored graph partitioning, or: gerrymandering at its worst, Bisecting a 4-connected graph with three resource sets, Solving the 2-rooted mini-max spanning forest problem by branch-and-bound, Representations of graphs and networks (coding, layouts and embeddings), An \(O(k^ 2 n^ 2)\) algorithm to find a \(k\)-partition in a \(k\)- connected graph, The even adjacency split problem for graphs, Flight gate scheduling with respect to a reference schedule, New bounds and constraint propagation techniques for the clique partitioning problem, A robust algorithm for bisecting a triconnected graph with two resource sets, FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Planar 3DM is NP-complete
• On partitioning the edges of graphs into connected subgraphs
• Max-Min Tree Partitioning
• The NP-Completeness of Some Edge-Partition Problems
• Planar Formulae and Their Uses
• The Recognition of Series Parallel Digraphs
• Two-Processor Scheduling with Start-Times and Deadlines
• A homology theory for spanning tress of a graph
• Paths, Trees, and Flowers
• On the completeness of a generalized matching problem