Finding Approximate Separators and Computing Tree Width Quickly

We show that for any fixed k , there is a linear-time algorithm which given a graph G either: (i) finds a cutset X of G with | X | ≤ k such that no component of G – X contains more than 3/4| G – X | vertices, or (ii) determines that for any set X of vertices of G with | X | ≤ k , there is a component of G – X which contains more than 2/3| G – X | vertices.

Authors

• Bruce A. Reed

Keywords

No keywords are indexed for this paper.