Max-min partitioning of grid graphs into connected components

DOI<115::AID-NET4>3.0.CO;2-E 10.1002/(SICI)1097-0037(199809)32:2<115::AID-NET4>3.0.CO;2-EzbMath0990.05117OpenAlexW1977623721MaRDI QIDQ4540070

Mario Lucertini, Bruno Simeone, Isabella Lari, Ronald I. Becker

Publication date: 21 July 2002

Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199809)32:2<115::aid-net4>3.0.co;2-e

zbMATH Keywords

partitioningerror estimatesmax-min problemmin-max problemrectangular grid graphshifting algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

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 ⋮ Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs ⋮ Max-min weight balanced connected partition ⋮ Improved algorithms for path partition and related problems ⋮ Approximation and parameterized algorithms for balanced connected partition problems ⋮ Balanced connected partitions of graphs: approximation, parameterization and lower bounds ⋮ Connected graph partitioning with aggregated and non‐aggregated gap objective functions ⋮ Balanced Connected Partitioning of Unweighted Grid Graphs ⋮ Uniform and most uniform partitions of trees ⋮ Partitioning a matrix with non-guillotine cuts to minimize the maximum cost ⋮ Partitioning a graph into balanced connected classes: formulations, separation and experiments ⋮ Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning ⋮ On a 2-dimensional equipartition problem ⋮ Unnamed Item ⋮ Path equipartition in the Chebyshev norm ⋮ Combinatorial approximation algorithms for the maximum bounded connected bipartition problem