Partitioning a graph into balanced connected classes: formulations, separation and experiments
From MaRDI portal
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) 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) Programming involving graphs or networks (90C35)
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
- 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
- A Shifting Algorithm for Min-Max Tree Partitioning
- 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
- 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?)
- Max-min partitioning of grid graphs into connected components
- Max-Min Tree Partitioning
- 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
(19)- Political districting to minimize cut edges
- An overview of graph covering and partitioning
- Approximation algorithms for the maximum bounded connected bipartition problem
- Cut and flow formulations for the balanced connected k-partition problem
- Mathematical political districting taking care of minority groups
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- Cardinality constrained connected balanced partitions of trees under different criteria
- A mixed integer linear programming model and variable neighborhood search for maximally balanced connected partition problem
- Max-min weight balanced connected partition
- The Capacitated and Economic Districting Problem
- Approximation and parameterized algorithms for balanced connected partition problems
- 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
- Polyhedral approach to weighted connected matchings in general graphs
- Fair and efficient graphical resource allocation with matching-induced utilities
- Optimizing connected components graph partitioning with minimum size constraints using integer programming and spectral clustering techniques
- Perfect hierarchical matchings in graphs
- Maximin share fair division of a k-uniform hypergraph
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)
