DIMACS Theory of Computing Seminar
A simple approximation algorithm for multiway separators
- Guy Even
- DIMACS Seminar Room 431, CoRE Building
- Busch Campus, Rutgers University
- 4:30 PM
- Thursday, October 19, 1995
Let G(V,E) denote a graph with edge capacities. A k-sector is a
partitioning of the vertices of a graph into k sets of almost equal
size. The cost of a k-sector equals the sum of the capacities of the
edges connecting vertices that belong to different sets. We present
an algorithm that partitions the vertices of a graph into at most k
parts, where each part contains at most 2|V|/k vertices. The sum of
the capacities of the edges that connect vertices that belong to
different parts is at most O(log |V|) times the cost of an optimal
k-sector. This result improves over Tragoudas' algorithm in
which the approximation factor is O(log k log |V|).
We also present an algorithm that computes a separator whose cost is
at most O(log n) times the cost of an optimal bisector. This
algorithm does not improve over the Leighton-Rao algorithm, however,
the analysis of this algorithm is simpler.
All our algorithms are applicable also to directed graphs and to
Joint work with Seffi Naor, Satish Rao, and Baruch Schieber.
Document last modified on October 11, 1995