215 citations · 689 across the 60 of their papers we have counts for
3 papers · 1 filter
Minimum -- Cuts with Fewer Cut Queries
Yonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya
We study the problem of computing a minimum -- cut in an unweighted, undirected graph via \emph{cut queries}. In this model, the input graph is accessed through an oracle tha…
Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions
Martin G. Herold, Danupon Nanongkai, Joachim Spoerhase +2
Geometric data structures have been extensively studied in the regime where the dimension is much smaller than the number of input points. But in many scenarios in Machine Learning…
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…