8 citations · 13 across the 11 of their papers we have counts for
18 papers
The Power of the Score Sequence of a Tournament
Prantar Ghosh, Sahil Kuchlous, Shravan Mehra +1
What problems can one solve on a tournament if only its score sequence is known? Tournaments are oriented complete graphs that form an extensively-studied class of directed graphs…
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…
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…
Shortcuts and Transitive-Closure Spanners Approximation
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay +1
We study polynomial-time approximation algorithms for two closely-related problems, namely computing shortcuts and transitive-closure spanners (TC spanners). For a directed unweigh…
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
Sepehr Assadi, Prantar Ghosh, Bruno Loff +2
The following question arises naturally in the study of graph streaming algorithms: "Is there any graph problem which is "not too hard", in that it can be solved efficiently with t…
Finding a Small Vertex Cut on Distributed Networks
Yonggang Jiang, Sagnik Mukhopadhyay
We present an algorithm for distributed networks to efficiently find a small vertex cut in the CONGEST model. Given a positive integer , our algorithm can, with high probability…