Max-min partitioning of grid graphs into connected components

DOI10.1002/(SICI)1097-0037(199809)32:2%3C115::AID-NET4%3E3.0.CO;2-EzbMATH Open0990.05117OpenAlexW1977623721MaRDI QIDQ4540070FDOQ4540070

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

Publication date: 21 July 2002

Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199809)32:2%3C115::aid-net4%3E3.0.co;2-e

Recommendations

• A polynomial-time algorithm for max-min partitioning of ladders
• Partitioning a Multi-weighted Graph to Connected Subgraphs of Almost Uniform Size
• On a 2-dimensional equipartition problem
• A 7/6-approximation algorithm for the max-min connected bipartition problem on grid graphs
• Graph-Theoretic Concepts in Computer Science

zbMATH Keywords

error estimatesmax-min problempartitioningmin-max problemrectangular grid graphshifting algorithm

Mathematics Subject Classification ID

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

Cited In (25)

• An overview of graph covering and partitioning
• A polynomial-time algorithm for max-min partitioning of ladders
• Improved algorithms for path partition and related problems
• Combinatorial approximation algorithms for the maximum bounded connected bipartition problem
• Title not available (Why is that?)
• Min-Max Graph Partitioning and Small Set Expansion
• Minimal rectangular partitions of digitized blobs
• Title not available (Why is that?)
• Uniform and most uniform partitions of trees
• Path equipartition in the Chebyshev norm
• Partitioning a graph into balanced connected classes: formulations, separation and experiments
• Connected graph partitioning with aggregated and non‐aggregated gap objective functions
• Approximation algorithms for min-max generalization problems
• Fully polynomial-time approximation schemes for the max-min connected partition problem on interval graphs
• A 7/6-approximation algorithm for the max-min connected bipartition problem on grid graphs
• Partitioning a graph into minimum gap components
• On a 2-dimensional equipartition problem
• Balanced connected partitioning of unweighted grid graphs
• Approximation and parameterized algorithms for balanced connected partition problems
• Approximation algorithms for the maximum bounded connected bipartition problem
• Balanced connected partitions of graphs: approximation, parameterization and lower bounds
• Partitioning a matrix with non-guillotine cuts to minimize the maximum cost
• Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
• Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs
• Max-min weight balanced connected partition

This page was built for publication: Max-min partitioning of grid graphs into connected components

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4540070)