Moments of Inertia and Graph Separators

Keith D. Gremban (), Gary L. Miller () and Shang-Hua Teng ()
Additional contact information
Keith D. Gremban: CTA Inc
Gary L. Miller: Carnegie Mellon University
Shang-Hua Teng: Carnegie Mellon University

Journal of Combinatorial Optimization, 1997, vol. 1, issue 1, No 4, 79-104

Abstract: Abstract Graphs that arise from the finite element or finite difference methods often include geometric information such as the coordinates of the nodes of the graph. The geometric separator algorithm of Miller, Teng, Thurston, and Vavasis uses some of the available geometric information to find small node separators of graphs. The algorithm utilizes a random sampling technique based on the uniform distribution to find a good separator. We show that sampling from an elliptic distribution based on the inertia matrix of the graph can significantly improve the quality of the separator. More generally, given a cost function f on the unit d-sphere Ud, we can define an elliptic distribution based on the second moments of f. The expectation of f with respect to the elliptic distribution is less than or equal to the expectation with respect to the uniform distribution, with equality only in degenerate cases. We also demonstrate experimentally that the benefit gained by the use of the additional geometric information is significant. Some previous algorithms have used the moments of inertia heuristically, and suffer from extremely poor worst case performance. This is the first result, to our knowledge, that incorporates the moments of inertia into a provably good strategy.

Keywords: Cost Function; Uniform Distribution; Discrete Geometry; Good Separator; Degenerate Case (search for similar items in EconPapers)
Date: 1997
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009763020645 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:1:y:1997:i:1:d:10.1023_a:1009763020645

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009763020645

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().