# ICS 269, Spring 2002: Theory Seminar

## 18 October 2002:

Title: Algorithms for Fault-Tolerant Routing in Circuit Switched Networks

Speaker: Amitabha Bagchi

Abstract:
We consider the *k* edge-disjoint paths problem
(*k*-EDP), a generalization of the well known edge-disjoint paths
problem. Given a graph *G*=(*V,E*) and a set of terminal pairs (or
requests) *T*, the problem is to find a maximum subset of the pairs in
*T* for which it is possible to select paths such that each pair is
connected by *k* edge-disjoint paths and the paths for different pairs
are mutually disjoint. To the best of our knowledge, no nontrivial
result is known for this problem for *k*>1. To measure the performance
of our algorithms we use the recently introduced flow number *F* of a
graph. This parameter is known to fulfill *F=O*(*Delta alpha*^{-1} log
*n*), where *Delta* is the maximum degree and *alpha* is the edge
expansion of *G*. We show that a simple, greedy online algorithm
achieves a competitive ratio of *O*(*k*^{3} *F*), which naturally
extends the best known bound of *O*(*F*) for *k*=1 to higher *k*. To
achieve this competitive ratio, we introduce a new method of
converting a system of *k* disjoint paths into a system of *k*
length-bounded disjoint paths.

In addition, we study the *k disjoint flows problem* (*k*-DFP),
which is a generalization of the previously studied unsplittable flow
problem (UFP). The difference between the *k*-DFP and the *k*-EDP is
that now we consider a graph with edge capacities and our requests are
allowed to have arbitrary demands *d*_{i}. The aim is to find a subset
of requests of maximum total demand for which it is possible to select
flow paths such that all the capacity constraints are maintained and
each selected request with demand *d*_{i} is connected by *k* disjoint
paths, each of flow value *d*_{i}/k.

This talk is based on work done jointly with Amitabh Chaudhary,
Christian Scheideler and Petr Kolman.