Equi-partitioning of Higher-dimensional Hyper-rectangular Grid Graphs
Vol. 11, no. 1, pp. 83-98, 2007. Regular paper.
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 |
xi −
yi| = 1 and
xj=
yj for all
j ≠
i.
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.