Location: MF 11/12

Speaker: Dylan Hyatt-Denesik (TU/e)

Title: Approximation Algorithm in Survivable Network Design

Abstract:
The problem of flexible graph connectivity is a new and exciting topic in the field of survivable network design. In conventional survivable network design problems,  one is asked to find a subgraph such that each vertex pair is connected by a given nonnegative number of edge (or vertex) disjoint paths. One can interpret the requirement that vertices u and v are connected by k>0 edge (or node) disjoint paths as meaning that u and v are part of the same connected component even when k-1 edges (or nodes) have been deleted.

In (p,q)-Flexible Graph Connectivity, we partition our edges (or nodes), into “safe” and “unsafe”, and we are asked to find a subgraph containing at least p many edge (or node) disjoint paths between vertices, while also requiring that if q “unsafe” edges (or nodes) are deleted, we still have p between every vertex pair. In this talk we will consider an approximation algorithm for the (1,1)-FGC problem with respect to node connectivity, and a brief overview of results for other problems.