Tata Institute of Fundamental Research
Finding Sparse Vertex Cuts in Semi-Random Instances
STCS Colloquium
Speaker:
Anand Louis (Indian Institute of Science
Department of Computer Science
and Automation
Bangalore)
Organiser:
Prahladh Harsha
Date:
Tuesday, 16 Apr 2019, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: Graph partitioning problems are a central topic of research in the study of algorithms and complexity theory. One of the central problems studied in this field is the problem of computing the set having the least vertex expansion. For a graph G, the vertex expansion of a set S of vertices is defined as the ratio of the number of vertices in the boundary of S to the size of S. Computing the set of vertices having the least vertex expansion is an NP-hard problem.
In this talk, I'll describe a natural semi-random model of graphs with sparse vertex cuts, and present approximation algorithms for the problem of computing the sparsest vertex cut in this model. Based on joint work with Rakesh Venkat.
| Speaker: | Anand Louis (Indian Institute of Science Department of Computer Science and Automation Bangalore) |
| Organiser: | Prahladh Harsha |
| Date: | Tuesday, 16 Apr 2019, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: Graph partitioning problems are a central topic of research in the study of algorithms and complexity theory. One of the central problems studied in this field is the problem of computing the set having the least vertex expansion. For a graph G, the vertex expansion of a set S of vertices is defined as the ratio of the number of vertices in the boundary of S to the size of S. Computing the set of vertices having the least vertex expansion is an NP-hard problem.
In this talk, I'll describe a natural semi-random model of graphs with sparse vertex cuts, and present approximation algorithms for the problem of computing the sparsest vertex cut in this model. Based on joint work with Rakesh Venkat.
In this talk, I'll describe a natural semi-random model of graphs with sparse vertex cuts, and present approximation algorithms for the problem of computing the sparsest vertex cut in this model. Based on joint work with Rakesh Venkat.