- This event has passed.
CO seminar – Dylan Hyatt-Denesik
December 8 @ 12:30 - 13:30
Location: MF 11/12
Speaker: Dylan Hyatt-Denesik (TU/e)
Title: Approximation Algorithm in Survivable Network Design
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.