215 citations · 689 across the 60 of their papers we have counts for
5 papers · 1 filter
Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
The study of graph products is a major research topic and typically concerns the term , e.g., to show that . In this paper, we study graph products in a no…
Almost-Tight Distributed Minimum Cut Algorithms
Danupon Nanongkai, Hsin-Hao Su
We study the problem of computing the minimum cut in a weighted distributed message-passing networks (the CONGEST model). Let be the minimum cut, be the number of nodes in…
Distributed Symmetry Breaking in Hypergraphs
Shay Kutten, Danupon Nanongkai, Gopal Pandurangan +1
Fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been recognized as important by the community, and studied extensively in (stan…
Brief Announcement: Almost-Tight Approximation Distributed Algorithm for Minimum Cut
Danupon Nanongkai
In this short paper, we present an improved algorithm for approximating the minimum cut on distributed (CONGEST) networks. Let be the minimum cut. Our algorithm can compute …
Distributed Approximation Algorithms for Weighted Shortest Paths
Danupon Nanongkai
A distributed network is modeled by a graph having nodes (processors) and diameter . We study the time complexity of approximating {\em weighted} (undirected) shortest paths…