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.]
Done