@Article{grady2006:isoperimetric_b,
author = {Leo Grady and Eric L. Schwartz},
title = {Isoperimetric partitioning: a new algorithm for
graph partitioning},
key = {graph theory isoperimetric},
journal = {SIAM Journal of Scientific Computing},
volume = 27,
number = 6,
pages = {1844--1866},
year = 2006,
abstract = {We present a new algorithm for graph partitioning
based on optimization of the combinatorial
isoperimetric constant. It is shown empirically that
this algorithm is competitive with other global
partitioning algorithms in terms of partition
quality. The isoperimetric algorithm is easy to
parallelize, does not require coordinate
information, and handles nonplanar graphs, weighted
graphs, and families of graphs which are known to
cause problems for other methods. Compared to
spectral partitioning, the isoperimetric algorithm
is faster and more stable. An exact circuit analogy
to the algorithm is also developed with a natural
random walks interpretation. The isoperimetric
algorithm for graph partitioning is implemented in
our publicly available Graph Analysis Toolbox [L.
Grady, Ph.D. thesis, Boston University, Boston, MA,
2004], [L. Grady and E. L. Schwartz, Technical
report TR-03-021, Boston University, Boston, MA,
2003] for MATLAB obtainable at
http://eslab.bu.edu/software/graphanalysis/. This
toolbox was used to generate all of the results
compiled in the tables of this paper.},
keywords = {graph partitioning, spectral partitioning,
isoperimetric problem, graph theory, linear
equations},
ams_subject = {91B28, 91B30, 60J75, 30A36},
DOI = {10.1137/040609008},
url = {http://www.siam.org/journals/sisc/27-6/60900.html},
datestr = 200603,
}