A Separator Theorem for Chordal Graphs
Collections
Author
Gilbert, John R.
Rose, Donald J.
Abstract
Chordal graphs are undirected graphs in which every cycle of length at least four has a chord. They are sometimes called rigid circuit graphs or perfect elimination graphs; the last name reflects their utility in modelling Gaussian elimination on sparse matrices. The main result of this paper is that a chordal graph with $n$ vertices and $m$ edges can be cut in half by removing $O(\sqrt{m})$ vertices. A similar result holds if the vertices have non-negative weights and we want to bisect the graph by weight, or even if we want to bisect the graph simultaneously by several unrelated sets of weights.
Date Issued
1982-10
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR82-523
Type
technical report