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