- This event has passed.

# CO seminar – Dylan Hyatt-Denesik

## December 8, 2023 @ 12:30 - 13:30

**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.