Equi-partitioning of Higher-dimensional Hyper-rectangular Grid Graphs
Athula D. A. Gunawardena, Robert R. Meyer · Journal of Graph Algorithms and Applications · 2007
A d-dimensional grid graph G is the graph on a finite subset in the integer lattice Z d 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 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. Although several efficient 2-dimensional heuristics which exploit the geometry of the grid are available in the literature, very little progress has been made in constructing similar algorithms for partitioning higher dimensional (d> 2) grid graphs. 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 [ Discrete Appl. Math., 82 (1998), pp. 193–207]. It runs in linear time in the number of nodes (O(n), n = |G|) when each Ki is O(n 1/d). Utilizing a result due to Bollabas and Leader [Combinatorica, 11.4 (1991), pp. 299–314], we construct an algorithm to calculate 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.