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


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