Thursday, November 2 2023
11:30 - 13:00

Alladi Ramakrishnan Hall

Determinantal Sieving

Sanjay S.

IMSc

Given a graph G and subsets of vertices S and T, an (S,T)-linkage in G is a collection of vertex disjoint paths that start in S and end in T.
In this talk, we will see a randomized algorithm that determines whether there is an (S,T)-linkage that contains at least k vertices in total.

The talk is a presentation of some results in the following paper:
Determinantal Sieving by Eduard Eiben, Tomohiro Koana, Magnus Wahlström.
arxiv.org/abs/2304.02091 (To appear in the proceedings of SODA24)

[This is part of credit seminar for Sanjay.]



Download as iCalendar

Done