Geodesic
Equi-partitioning of Higher-dimensional Hyper-rectangular Grid Graphs
Journal of Graph Algorithms and Applications, Tome 11 (2007) no. 1, pp. 83-98.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2007_11_1_a3,
     author = {Athula Gunawardena and Robert Meyer},
     title = {Equi-partitioning of {Higher-dimensional} {Hyper-rectangular} {Grid} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {83--98},
     publisher = {mathdoc},
     volume = {11},
     number = {1},
     year = {2007},
     doi = {10.7155/jgaa.00138},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00138/}
}
TY  - JOUR
AU  - Athula Gunawardena
AU  - Robert Meyer
TI  - Equi-partitioning of Higher-dimensional Hyper-rectangular Grid Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2007
SP  - 83
EP  - 98
VL  - 11
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00138/
DO  - 10.7155/jgaa.00138
LA  - en
ID  - JGAA_2007_11_1_a3
ER  - 
%0 Journal Article
%A Athula Gunawardena
%A Robert Meyer
%T Equi-partitioning of Higher-dimensional Hyper-rectangular Grid Graphs
%J Journal of Graph Algorithms and Applications
%D 2007
%P 83-98
%V 11
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00138/
%R 10.7155/jgaa.00138
%G en
%F JGAA_2007_11_1_a3
Athula Gunawardena; Robert Meyer. Equi-partitioning of Higher-dimensional Hyper-rectangular Grid Graphs. Journal of Graph Algorithms and Applications, Tome 11 (2007) no. 1, pp. 83-98. doi : 10.7155/jgaa.00138. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00138/

Cité par Sources :