5 papers
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…
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…
Negative-Weight Single-Source Shortest Paths in Near-linear Time
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
We present a randomized algorithm that computes single-source shortest paths (SSSP) in time when edge weights are integral and can be negative. This essential…
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…
Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao +5
This paper presents parallel, distributed and quantum algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework t…