Max-min partitioning of grid graphs into connected components

DOI10.1002/(SICI)1097-0037(199809)32:2%3C115::AID-NET4%3E3.0.CO;2-EMaRDI QIDQ4540070zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

error estimatesmax-min problemmin-max problempartitioningrectangular grid graphshifting algorithm

Mathematics Subject Classification ID

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

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

Cited in

(27)

• Path equipartition in the Chebyshev norm
• Uniform and most uniform partitions of trees
• On a 2-dimensional equipartition problem
• Partitioning a graph into balanced connected classes: formulations, separation and experiments
• Combinatorial approximation algorithms for the maximum bounded connected bipartition problem
• An overview of graph covering and partitioning
• Approximation algorithms for the maximum bounded connected bipartition problem
• Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
• 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
• Approximation algorithms for min-max generalization problems
• Minimal rectangular partitions of digitized blobs
• 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
• scientific article; zbMATH DE number 480527 (Why is no real title available?)
• scientific article; zbMATH DE number 1026281 (Why is no real title available?)
• Balanced connected partitioning of unweighted grid graphs
• Partitioning a graph into minimum gap components
• Min-Max Graph Partitioning and Small Set Expansion
• scientific article; zbMATH DE number 2230227 (Why is no real title available?)
• A polynomial-time algorithm for max-min partitioning of ladders
• Partitioning a matrix with non-guillotine cuts to minimize the maximum cost
• 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
• Connected partitions via connected dominating sets

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)