Density Graphs and Separators
Permanent Link(s)
Collections
Author
Miller, Gary L.
Vavasis, Stephen A.
Abstract
We propose a class of graphs that would occur naturally in finite-element problems, and we prove a bound on separators for this class of graphs. For three-dimensional graphs, our separator bound is $O(N^{2/3})$. We also propose a simple randomized algorithm to find this separator in $O(N)$ time. Such an algorithm would be used as a preprocessing step for the domain decomposition method of efficiently solving a finite-element problem on a parallel computer. This paper generalizes "local graphs" of Vavasis [1990] to the case of graphs with varying densities of nodes. It also generalizes aspects of Miller and Thurston's [1990] "stable graphs."
Date Issued
1990-11
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1169
Type
technical report