Partitioning a graph into balanced connected classes: formulations, separation and experiments

DOI10.1016/j.ejor.2020.12.059zbMath1487.90626OpenAlexW3118973667MaRDI QIDQ2030323

Flávio K. Miyazawa, Yoshiko Wakabayashi, Matheus J. Ota, Phablo F. S. Moura

Publication date: 7 June 2021

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2020.12.059

zbMATH Keywords

integer programmingbranch-and-cutseparation algorithmbalanced partitionconnected partition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

An overview of graph covering and partitioning ⋮ Approximation algorithms for the maximum bounded connected bipartition problem ⋮ The Capacitated and Economic Districting Problem ⋮ Approximation and parameterized algorithms for balanced connected partition problems ⋮ Cardinality constrained connected balanced partitions of trees under different criteria ⋮ Balanced connected partitions of graphs: approximation, parameterization and lower bounds ⋮ Vertex covering with capacitated trees ⋮ Connected graph partitioning with aggregated and non‐aggregated gap objective functions ⋮ Mathematical political districting taking care of minority groups ⋮ Political districting to minimize cut edges

Uses Software

• LEMON

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A mixed integer linear programming model and variable neighborhood search for maximally balanced connected partition problem
• A linear-time algorithm for four-partitioning four-connected planar graphs
• The disjoint paths problem in quadratic time
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• On the complexity of partitioning graphs into connected subgraphs
• The \(\gamma\)-connected assignment problem
• An \(O(k^ 2 n^ 2)\) algorithm to find a \(k\)-partition in a \(k\)- connected graph
• Clustering on trees
• Most uniform path partitioning and its use in image processing
• Cut and flow formulations for the balanced connected \(k\)-partition problem
• FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS
• Shifting algorithms for tree partitioning with general weighting functions
• A new approach to the maximum-flow problem
• Max-Min Tree Partitioning
• A Shifting Algorithm for Min-Max Tree Partitioning
• A homology theory for spanning tress of a graph
• Max-min partitioning of grid graphs into connected components
• Doubly Balanced Connected Graph Partitioning
• Balanced Partition of Minimum Spanning Trees