## Min-Max-Boundary Domain Decomposition

**Authors:**
Marcos Kiwi,
Daniel A. Spielman
and Shang-Hua Teng.
**Bibliographic Information:**
Appeared in Special issue of
Theoretical Computer Science for COCOON'98,
volume 261, issue 2, 2001, pp. 253-266

An extended abstract
appeared in
* Proceedings of the 4-th Annual International Computing
and Combinatorics Conference - COCOON, 1998.*

## Abstract:

Motivated by domain decomposition, one of the most effective and popular parallel numerical techniques, we
study the following {\sf min-max boundary} multi-way partitioning problem: Given a graph $G$ and a positive
integer $k$, we would like to divide $G$ into $k$ subgraphs $G_1,...,G_k$ (by removing edges) such that (i) $|G_i|
= \Theta(n/k)$ for all $i$ in the range $1\leq i\leq k$; and (ii) the maximum boundary size of any subgraph (the
set of edges connecting it with other subgraphs) is minimized.
We obtain the following result: Let $G$ be a well-shaped mesh in $d$ dimensions. Then $G$ can be partitioned
in $k$ subgraphs $G_1$,...,$G_k$ such that for all $i$ in the range $1\leq i\leq k$, $G_i$ has $\Theta(n/k)$
vertices and the number of edges connecting $G_i$ with other subgraphs is bounded by $O(n/k)^{1-1/d}$.
Similar results (with $d = 2$) are also given for planar graphs and graphs with bounded genus and forbidden
minors. Furthermore, our algorithm can find such a partition in $O(n\log k)$ time. We also extend this result to
weighted graphs and vertex-based graph decomposition.
You can download this paper as
Postscript,
compressed Postscript,
PDF, or
compressed PDF.

Daniel A. Spielman
Last modified: Sun Aug 26 11:57:40 2001