Equi-partitioning of Higher-dimensional Hyper-rectangular Grid Graphs

Authors

  • Athula Gunawardena
  • Robert Meyer

DOI:

https://doi.org/10.7155/jgaa.00138

Abstract

A d-dimensional grid graph G is the graph on a finite subset in the integer lattice Zd in which a vertex x = (x1, x2, …, xn) is joined to another vertex y = (y1, y2, …, yn) if for some i we have |xiyi| = 1 and xj=yj for all ji. G is hyper-rectangular if its set of vertices forms [K1] ×[K2] ×…×[Kd], where each Ki is a nonnegative integer, [Ki] = {0, 1, …, Ki−1}. The surface area of G is the number of edges between G and its complement in the integer grid Zd. We consider the Minimum Surface Area problem, MSA(G,V), of partitioning G into subsets of cardinality V so that the total surface area of the subgraphs corresponding to these subsets is a minimum. We present an equi-partitioning algorithm for higher dimensional hyper-rectangles and establish related asymptotic optimality properties. Our algorithm generalizes the two dimensional algorithm due to Martin []. It runs in linear time in the number of nodes (O(n), n=|G|) when each Ki is O(n1/d). Utilizing a result due to Bollabas and Leader [], we derive a useful lower bound for the surface area of an equi-partition. Our computational results either achieve this lower bound (i.e., are optimal) or stay within a few percent of the bound.

Downloads

Download data is not yet available.

Downloads

Published

2007-01-01

How to Cite

Gunawardena, A., & Meyer, R. (2007). Equi-partitioning of Higher-dimensional Hyper-rectangular Grid Graphs. Journal of Graph Algorithms and Applications, 11(1), 83–98. https://doi.org/10.7155/jgaa.00138

Issue

Section

Articles

Categories