ABSTRACT
Many load balancing problems that arise in scientific computing applications ask to partition a graph with weights on the vertices and costs on the edges into a given number of almost equally-weighted parts such that the maximum boundary cost over all parts is small.Here, this partitioning problem is considered for boundeddegree graphs G ≡ (V,E) with edge costs c: E → R+ that have a p-separator theorem for some p > 1, i.e., any (arbitrarily weighted) subgraph of G can be separated into two parts of roughly the same weight by removing separator S⊆V such that the edges incident to S in the subgraph have total cost at most proportional to (Εecp<over>e)1/p, where the sum is over all edges in the subgraph.We show for all positive integers k and weights w that the vertices of G can be partitioned into k parts such that the weight of each part differs from the average weight Εv∈V wv<over>k by less than maxv∈V wv, and the boundary edges of each part have cost at most proportional to (Εe∈ cp<over>e/k)1/p + maxe∈E ce. The partition can be computed in time nearly proportional to the time for computing a separator S of G.Our upper bound on the boundary costs is shown to be tight up to a constant factor for infinitely many instances with a broad range of parameters. Previous results achieved this bound only if one has c ≡ 1, w ≡ 1, and one allows parts with weight exceeding the average by a constant fraction.
- N. Alon, P. Seymour, and R. Thomas. A separator theorem for graphs with an excluded minor and its applications. In STOC, pages 293--299, 1990. Google ScholarDigital Library
- H. Djidjev. Partitioning planar graphs with vertex costs: Algorithms and applications. Algorithmica, 28(1):51--75, 2000.Google ScholarDigital Library
- M. A. Kiwi, D. A. Spielman, and S. H. Teng. Min-max-boundary domain decomposition. Theor. Comput. Sci., 261(2):253--266, 2001. Google ScholarDigital Library
- R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177--189, 1979.Google ScholarDigital Library
- G. L. Miller, S. H. Teng, W. Thurston, and S. A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. J. ACM, 44(1):1--29, 1997. Google ScholarDigital Library
- G. L. Miller, S. H. Teng, W. Thurston, and S. A. Vavasis. Geometric separators for finite-element meshes. SIAM J. Sci. Comput., 19(2):364--386, 1998. Google ScholarDigital Library
- H. D. Simon and S.-H. Teng. How good is recursive bisection? SIAM Journal on Scientific Computing, 18(5):1436--1445, 1997. Google ScholarDigital Library
- D. A. Spielman and S.-H. Teng. Spectral partitioning works: Planar graphs and finite element meshes. In FOCS, pages 96--105, 1996. Google ScholarDigital Library
- D. Steurer. Tight bounds on the min-max boundary decomposition cost of weighted graphs. arXiv, cs.DS/0606001, 2006.Google Scholar
Index Terms
- Tight bounds for the Min-Max boundary decomposition cost of weighted graphs
Recommendations
b-coloring of tight graphs
A coloring c of a graph G=(V,E) is a b-coloring if in every color class there is a vertex whose neighborhood intersects every other color class. The b-chromatic number of G, denoted @g"b(G), is the greatest integer k such that G admits a b-coloring with ...
Partitioning planar graphs with costs and weights
A graph separator is a set of vertices or edges whose removal divides an input graph into components of bounded size. This paper describes new algorithms for computing separators in planar graphs as well as techniques that can be used to speed up the ...
Boundary vertices in graphs
The distance d(u, v) between two vertices u and v in a nontrivial connected graph G is the length of a shortest u-v path in G. For a vertex v of G, the eccentricity e(v) is the distance between v and a vertex farthest from v. A vertex v of G is a ...
Comments