### DIMACS Theoretical Computer Science Seminar

Title: Fault-Tolerant Spanners and their Applications

Speaker: **Hairong Zhao**, NJIT

Date: March 1, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Spanners are spanning subgraphs that contain short paths between
the vertices that are connected by an edge in the original graph.
Spanners provide a sparse or economic representation of graphs.
They have many applications in robotics, graph theory, network
topology design, distributed systems. Fault-tolerant spanners, are
spanning subgraphs that remain as spanners even after removing a
vertex or an edge. Fault-tolerant spanners are natural extensions
of spanners to graphs resistant to edge and vertex removal.

In this talk, I will discuss two different techniques of
constructing ``good'' fault-tolerant spanners. First, I will show that a
generalized greedy algorithm constructs $k$-fault tolerant
geometric spanners such that both the vertex degree and total
weight are optimal. I will also describe an efficient algorithm
for constructing near optimal fault-tolerant geometric spanners.
Then I will present a new different algorithm that constructs $1$-fault
tolerant spanners of planar graphs which at the same time is at
most a constant factor heavier than the minimum-weight
2-Edge-connected (or 2-vertex-connected) spanning subgraphs. This
is the first non-trivial result about fault-tolerant spanners
besides geometric graphs. Finally, I will demonstrate an
application of our spanner result to design a quasi-polynomial
time approximation scheme (QPTAS) for constructing a
minimum-weight 2-Edge-connected (or 2-vertex-connected) spanning
subgraphs of a weighted planar graph. Our result improves upon a
very recent result by Czumaj et.al. that finds a
$(1+\epsilon)$-approximation in time $n^{O(w(G)/OPT(G))}$.

Joint work with
Andre Berger (Emory), Artur Czumaj(NJIT),
Michelangelo Grigni(Emory), and Papa Sissokho (Emory)

See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html