Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00138
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.
|
Journal Supporters
|