# DIMACS Theory of Computing Seminar

## Title:

A simple approximation algorithm for multiway separators

## Speaker:

- Guy Even
- Technion

## Place:

- DIMACS Seminar Room 431, CoRE Building
- Busch Campus, Rutgers University

## Time:

- 4:30 PM
- Thursday, October 19, 1995

## Abstract:

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
node-separators.

Joint work with Seffi Naor, Satish Rao, and Baruch Schieber.

dimacs-www@dimacs.rutgers.edu
Document last modified on October 11, 1995