6 citations · 20 across the 19 of their papers we have counts for
4 papers · 1 filter
A Little Clairvoyance Is All You Need
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
We revisit the classical problem of minimizing the total flow time of jobs on a single machine in the online setting where jobs arrive over time. It has long been known that the Sh…
Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
Olivier Fischer, Yonggang Jiang, Sagnik Mukhopadhyay +1
Vertex connectivity and its variants are among the most fundamental problems in graph theory, with decades of extensive study and numerous algorithmic advances. The directed varian…
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak +1
We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph vertices and edges in time. This breaks the long-sta…
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay +1
A recent breakthrough by [LNPSY STOC'21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequ…