Partitioning a graph into balanced connected classes: formulations, separation and experiments
From MaRDI portal
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Recommendations
- Cut and flow formulations for the balanced connected \(k\)-partition problem
- Max-min weight balanced connected partition
- Approximation and inaproximability results on balanced connected partitions of graphs
- Approximation algorithms for maximally balanced connected graph partition
- Approximation algorithms for maximally balanced connected graph partition
Cites work
- scientific article; zbMATH DE number 432817 (Why is no real title available?)
- scientific article; zbMATH DE number 3603293 (Why is no real title available?)
- scientific article; zbMATH DE number 1256746 (Why is no real title available?)
- A Shifting Algorithm for Min-Max Tree Partitioning
- A homology theory for spanning tress of a graph
- A linear-time algorithm for four-partitioning four-connected planar graphs
- A mixed integer linear programming model and variable neighborhood search for maximally balanced connected partition problem
- A new approach to the maximum-flow problem
- An \(O(k^ 2 n^ 2)\) algorithm to find a \(k\)-partition in a \(k\)- connected graph
- Approximating the Maximally Balanced Connected Partition Problem in graphs
- Balanced Partition of Minimum Spanning Trees
- Clustering on trees
- 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
- Max-Min Tree Partitioning
- Max-min partitioning of grid graphs into connected components
- Most uniform path partitioning and its use in image processing
- On the complexity of partitioning graphs into connected subgraphs
- Shifting algorithms for tree partitioning with general weighting functions
- The -connected assignment problem
- The disjoint paths problem in quadratic time
Cited in
(15)- Mathematical political districting taking care of minority groups
- An overview of graph covering and partitioning
- A mixed integer linear programming model and variable neighborhood search for maximally balanced connected partition problem
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- The Capacitated and Economic Districting Problem
- Cardinality constrained connected balanced partitions of trees under different criteria
- Vertex covering with capacitated trees
- Connected graph partitioning with aggregated and non‐aggregated gap objective functions
- Cut and flow formulations for the balanced connected \(k\)-partition problem
- Polyhedral approach to weighted connected matchings in general graphs
- Approximation algorithms for the maximum bounded connected bipartition problem
- Approximation and parameterized algorithms for balanced connected partition problems
- Balanced connected partitions of graphs: approximation, parameterization and lower bounds
- Max-min weight balanced connected partition
- Political districting to minimize cut edges
This page was built for publication: Partitioning a graph into balanced connected classes: formulations, separation and experiments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2030323)
