Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. A Separator Theorem for Chordal Graphs

A Separator Theorem for Chordal Graphs

File(s)
82-523.pdf (1.03 MB)
82-523.ps (223.77 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6362
Collections
Computer Science Technical Reports
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
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR82-523
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance