Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00138
Equipartitioning of Higherdimensional Hyperrectangular Grid Graphs
Vol. 11, no. 1, pp. 8398, 2007. Regular paper.
Abstract A ddimensional grid graph G is the graph on a finite subset in the integer lattice Z^{d} in which
a vertex x = (x_{1}, x_{2}, …, x_{n})
is joined to another vertex y = (y_{1}, y_{2}, …, y_{n}) if for some i we have x_{i} − y_{i} = 1 and
x_{j}=y_{j} for all j ≠ i. G is hyperrectangular if its set of vertices forms
[K_{1}] ×[K_{2}] ×…×[K_{d}], where each K_{i} is a
nonnegative integer, [K_{i}] = {0, 1, …, K_{i}−1}.
The surface area of G is the number of edges between G
and its complement in the integer grid Z^{d}.
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 equipartitioning algorithm
for higher dimensional hyperrectangles
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 K_{i} is O(n^{1/d}).
Utilizing a result due to Bollabas and Leader [],
we
derive a useful lower bound
for the surface area of an equipartition. Our computational results either achieve
this lower bound (i.e., are optimal) or
stay within a few percent of the bound.
