Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Density Graphs and Separators
Authors: Miller, Gary L.
Vavasis, Stephen A.
Keywords: computer science
technical report
Issue Date: Nov-1990
Publisher: Cornell University
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."
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
90-1169.pdf1.99 MBAdobe PDFView/Open
90-1169.ps448.69 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us