Show simple item record

dc.contributor.authorDjidjev, Hristo N.
Gilbert, John
dc.date.accessioned 2017-08-02T22:03:23Z
dc.date.available 2017-08-02T22:03:23Z
dc.date.issued 1994-04
dc.identifier.urihttps://hdl.handle.net/1911/96441
dc.description.abstract A separator theorem for a class of graphs asserts that every graph in the class can be divided approximately in half by removing a set of vertices of specified size. Nontrivial separator theorems hold for several classes of graphs, including graphs of bounded genus and chordal graphs. We show that any separator theorem implies various weighted separator theorems. In particular, we show that if the vertices of the graph have real-valued weights, which maybe positive or negative, then the graph can be divided exactly in half according to weight. If k unrelated sets of weights are given, the graph can be divided simultaneously by all sets of weights. These results considerably strengthen earlier results of Gilbert, Lipton, and Tarjan: (1) for k=1 with the weights restricted to be nonnegative, and (2) for k > 1, nonnegative weights, and simultaneous division within a factor of (1 + e) of exactly in half.
dc.format.extent 19 pp
dc.language.iso eng
dc.rights You are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, but this permission is only for a period of forty-five (45) days from the most recent time that you verified that this technical report is still available from the Computer Science Department of Rice University under terms that include this permission. All other rights are reserved by the author(s).
dc.title Separators in Graphs with Negative and Multiple Vertex Weights
dc.type Technical report
dc.date.note April 1994
dc.identifier.digital TR94-226
dc.type.dcmi Text
dc.identifier.citation Djidjev, Hristo N. and Gilbert, John. "Separators in Graphs with Negative and Multiple Vertex Weights." (1994) https://hdl.handle.net/1911/96441.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record