On the complexity of partitioning graphs into connected subgraphs
From MaRDI portal
Publication:1057062
DOI10.1016/0166-218X(85)90008-3zbMath0562.68030WikidataQ56324173 ScholiaQ56324173MaRDI QIDQ1057062
Publication date: 1985
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of partitions of integers (05A17) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40)
Related Items
A linear-time algorithm for four-partitioning four-connected planar graphs ⋮ Algorithms for gerrymandering over graphs ⋮ Balanced connected graph partition ⋮ Finding good 2-partitions of digraphs. I. Hereditary properties ⋮ The complexity of the unit stop number problem and its implications to other related problems ⋮ Finding good 2-partitions of digraphs. II. Enumerable properties ⋮ Edge-disjoint packing of stars and cycles ⋮ FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS ⋮ An overview of graph covering and partitioning ⋮ Approximation algorithms for the maximum bounded connected bipartition problem ⋮ An exact algorithm for min-max hyperstructure equipartition with a connected constraint ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ More aspects of arbitrarily partitionable graphs ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Max-min weight balanced connected partition ⋮ Degree-constrained 2-partitions of graphs ⋮ Decomposing subcubic graphs into claws, paths or triangles ⋮ Reconfiguration of connected graph partitions ⋮ Approximation and parameterized algorithms for balanced connected partition problems ⋮ Approximation algorithm for the balanced 2-connected \(k\)-partition problem ⋮ A plane graph representation of triconnected graphs ⋮ 3D geo-graphs: efficient flip verification for the spherical zoning problem ⋮ Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs ⋮ Balanced connected partitions of graphs: approximation, parameterization and lower bounds ⋮ Connected graph partitioning with aggregated and non‐aggregated gap objective functions ⋮ Unnamed Item ⋮ A linear algorithm for bipartition of biconnected graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New bounds and constraint propagation techniques for the clique partitioning problem ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ Approximation algorithms for some min-max postmen cover problems ⋮ Parliament seating assignment problems ⋮ Star Partitions of Perfect Graphs ⋮ Flight gate scheduling with respect to a reference schedule ⋮ Bicolored graph partitioning, or: gerrymandering at its worst ⋮ Partitioning a graph into balanced connected classes: formulations, separation and experiments ⋮ Bisecting a 4-connected graph with three resource sets ⋮ On three polynomial kernels of sequences for arbitrarily partitionable graphs ⋮ Approximation algorithms for maximally balanced connected graph partition ⋮ Approximation algorithms for some minimum postmen cover problems ⋮ PARTITIONING TREES OF SUPPLY AND DEMAND ⋮ Decomposing Cubic Graphs into Connected Subgraphs of Size Three ⋮ On the Complexity of Computing the k-restricted Edge-connectivity of a Graph ⋮ Reconfiguration of connected graph partitions via recombination ⋮ Reconfiguration of connected graph partitions via recombination ⋮ The even adjacency split problem for graphs ⋮ Mondshein Sequences (a.k.a. (2,1)-Orders) ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Solving the 2-rooted mini-max spanning forest problem by branch-and-bound ⋮ Approximation algorithms for the maximally balanced connected graph tripartition problem ⋮ A robust algorithm for bisecting a triconnected graph with two resource sets ⋮ The parameterized complexity landscape of finding 2-partitions of digraphs ⋮ Political districting to minimize cut edges ⋮ The Price of Connectivity in Fair Division ⋮ On the complexity of partitioning a graph into a few connected subgraphs ⋮ An \(O(k^ 2 n^ 2)\) algorithm to find a \(k\)-partition in a \(k\)- connected graph
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
