An \(O(k^ 2 n^ 2)\) algorithm to find a \(k\)-partition in a \(k\)- connected graph

DOI10.1007/BF02939489zbMath0804.68104MaRDI QIDQ1322395

Jun Ma, Shaohan Ma

Publication date: 5 May 1994

Published in: Journal of Computer Science and Technology (Search for Journal in Brave)

zbMATH Keywords

graph algorithm\(k\)-partition of graphgraph vertex connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Related Items

A linear-time algorithm for four-partitioning four-connected planar graphs, An exact algorithm for min-max hyperstructure equipartition with a connected constraint, Max-min weight balanced connected partition, Partitioning a graph into balanced connected classes: formulations, separation and experiments, Unnamed Item

Cites Work

• On the complexity of partitioning graphs into connected subgraphs
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A homology theory for spanning tress of a graph
• Unnamed Item
• Unnamed Item