A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. - Parinya Chalermsook; Jittat Fakcharoenphol; Danupon Nanongkai (SODA, 2004)

Fast distributed random walks. - Atish Das Sarma; Danupon Nanongkai; Gopal Pandurangan (PODC, 2009)

Stackelberg Pricing is Hard to Approximate within 2-ε - Parinya Chalermsook; Bundit Laekhanukit; Danupon Nanongkai (CoRR, 2009)

Near-Optimal Sublinear Time Bounds for Distributed Random Walks - Atish Das Sarma; Danupon Nanongkai; Gopal Pandurangan; Prasad Tetali (CoRR, 2009)

Randomized Multi-pass Streaming Skyline Algorithms. - Atish Das Sarma; Ashwin Lall; Danupon Nanongkai; Jun (Jim) Xu (Proc. VLDB Endow., 2009)

Faster Algorithms for Semi-matching Problems (Extended Abstract). - Jittat Fakcharoenphol; Bundit Laekhanukit; Danupon Nanongkai (ICALP (1), 2010)

Efficient distributed random walks with applications. - Atish Das Sarma; Danupon Nanongkai; Gopal Pandurangan; Prasad Tetali (PODC, 2010)

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing. - Patrick Briest; Parinya Chalermsook; Sanjeev Khanna; Bundit Laekhanukit; Danupon Nanongkai (WINE, 2010)

Regret-Minimizing Representative Databases. - Danupon Nanongkai; Atish Das Sarma; Ashwin Lall; Richard J. Lipton; Jun (Jim) Xu (Proc. VLDB Endow., 2010)

Representative skylines using threshold-based preference distributions. - Atish Das Sarma; Ashwin Lall; Danupon Nanongkai; Richard J. Lipton; Jun (Jim) Xu (ICDE, 2011)

A tight unconditional lower bound on distributed randomwalk computation. - Danupon Nanongkai; Atish Das Sarma; Gopal Pandurangan (PODC, 2011)

A Tight Lower Bound on Distributed Random Walk Computation - Danupon Nanongkai; Atish Das Sarma; Gopal Pandurangan (CoRR, 2011)

Best-order streaming model. - Atish Das Sarma; Richard J. Lipton; Danupon Nanongkai (Theor. Comput. Sci., 2011)

Graph and geometric algorithms on distributed networks and databases. - Danupon Nanongkai (2011)

Brief announcement: maintaining large dense subgraphs on dynamic networks. - Atish Das Sarma; Ashwin Lall; Danupon Nanongkai; Amitabh Trehan (PODC, 2012)

Interactive regret minimization. - Danupon Nanongkai; Ashwin Lall; Atish Das Sarma; Kazuhisa Makino (SIGMOD Conference, 2012)

Dense Subgraphs on Dynamic Networks. - Atish Das Sarma; Ashwin Lall; Danupon Nanongkai; Amitabh Trehan (DISC, 2012)

Multi-Attribute Profit-Maximizing Pricing (Extended Abstract) - Parinya Chalermsook; Khaled M. Elbassioni; Danupon Nanongkai; He Sun 001 (CoRR, 2012)

Quantum Distributed Network Computing: Lower Bounds and Techniques - Michael Elkin; Hartmut Klauck; Danupon Nanongkai; Gopal Pandurangan (CoRR, 2012)

Distributed Verification and Hardness of Distributed Approximation. - Atish Das Sarma; Stephan Holzer; Liah Kor; Amos Korman; Danupon Nanongkai; Gopal Pandurangan; David Peleg; Roger Wattenhofer (SIAM J. Comput., 2012)

Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses. - Parinya Chalermsook; Bundit Laekhanukit; Danupon Nanongkai (FOCS, 2013)

Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks. - Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai (ICALP (2), 2013)

Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More. - Parinya Chalermsook; Bundit Laekhanukit; Danupon Nanongkai (SODA, 2013)

Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs. - Parinya Chalermsook; Shiva Kintali; Richard J. Lipton; Danupon Nanongkai (Chic. J. Theor. Comput. Sci., 2013)

The Distributed Complexity of Large-scale Graph Processing. - Hartmut Klauck; Danupon Nanongkai; Gopal Pandurangan; Peter Robinson 002 (CoRR, 2013)

Simple FPTAS for the subset-sums ratio problem. - Danupon Nanongkai (Inf. Process. Lett., 2013)

Distributed Random Walks. - Atish Das Sarma; Danupon Nanongkai; Gopal Pandurangan; Prasad Tetali (J. ACM, 2013)

An Approximate Restatement of the Four-Color Theorem. - Atish Das Sarma; Amita Gajewar; Richard J. Lipton; Danupon Nanongkai (J. Graph Algorithms Appl., 2013)

Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs. - Parinya Chalermsook; Bundit Laekhanukit; Danupon Nanongkai (FOCS, 2014)

Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation. - Parinya Chalermsook; Bundit Laekhanukit; Danupon Nanongkai (LATIN, 2014)

Can quantum communication speed up distributed computation? - Michael Elkin; Hartmut Klauck; Danupon Nanongkai; Gopal Pandurangan (PODC, 2014)

Brief announcement: almost-tight approximation distributed algorithm for minimum cut. - Danupon Nanongkai (PODC, 2014)

A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths. - Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai (SODA, 2014)

Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. - Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai (STOC, 2014)

Distributed approximation algorithms for weighted shortest paths. - Danupon Nanongkai (STOC, 2014)

Distributed Symmetry Breaking in Hypergraphs. - Shay Kutten; Danupon Nanongkai; Gopal Pandurangan; Peter Robinson 002 (DISC, 2014)

Almost-Tight Distributed Minimum Cut Algorithms. - Danupon Nanongkai; Hsin-Hao Su (DISC, 2014)

Polynomial-Time Algorithms for Energy Games with Special Weight Structures. - Krishnendu Chatterjee; Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai (Algorithmica, 2014)

Faster Algorithms for Semi-Matching Problems. - Jittat Fakcharoenphol; Bundit Laekhanukit; Danupon Nanongkai (ACM Trans. Algorithms, 2014)

Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs. - Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai (ICALP (1), 2015)

Social Network Monetization via Sponsored Viral Marketing. - Parinya Chalermsook; Atish Das Sarma; Ashwin Lall; Danupon Nanongkai (SIGMETRICS, 2015)

Distributed Computation of Large-scale Graph Problems. - Hartmut Klauck; Danupon Nanongkai; Gopal Pandurangan; Peter Robinson 002 (SODA, 2015)

Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. - Sayan Bhattacharya; Monika Henzinger; Danupon Nanongkai; Charalampos E. Tsourakakis (STOC, 2015)

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. - Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai; Thatchaphol Saranurak (STOC, 2015)

An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths. - Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai (CoRR, 2015)

New deterministic approximation algorithms for fully dynamic matching. - Sayan Bhattacharya; Monika Henzinger; Danupon Nanongkai (STOC, 2016)

Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and $O(n^{1/2-ε})$-Time. - Danupon Nanongkai; Thatchaphol Saranurak (CoRR, 2016)

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization. - Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai (SIAM J. Comput., 2016)

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrierand Derandomization. - Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai (Encyclopedia of Algorithms, 2016)

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. - Parinya Chalermsook; Marek Cygan; Guy Kortsarz; Bundit Laekhanukit; Pasin Manurangsi; Danupon Nanongkai; Luca Trevisan 001 (FOCS, 2017)

Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n5/4) Rounds. - Chien-Chung Huang 001; Danupon Nanongkai; Thatchaphol Saranurak (FOCS, 2017)

Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. - Danupon Nanongkai; Thatchaphol Saranurak; Christian Wulff-Nilsen (FOCS, 2017)

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time. - Sayan Bhattacharya; Monika Henzinger; Danupon Nanongkai (SODA, 2017)

Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time. - Danupon Nanongkai; Thatchaphol Saranurak (STOC, 2017)

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3n) Worst Case Update Time. - Sayan Bhattacharya; Monika Henzinger; Danupon Nanongkai (CoRR, 2017)

Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks. - Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai (ACM Trans. Algorithms, 2017)

A Faster Distributed Single-Source Shortest Paths Algorithm. - Sebastian Forster; Danupon Nanongkai (FOCS, 2018)

Dynamic Algorithms for Graph Coloring. - Sayan Bhattacharya; Deeparnab Chakrabarty; Monika Henzinger; Danupon Nanongkai (SODA, 2018)

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. - Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai (J. ACM, 2018)

A New Deterministic Algorithm for Dynamic Set Cover. - Sayan Bhattacharya; Monika Henzinger; Danupon Nanongkai (FOCS, 2019)

Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time. - Jan van den Brand; Danupon Nanongkai (FOCS, 2019)

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. - Jan van den Brand; Danupon Nanongkai; Thatchaphol Saranurak (FOCS, 2019)

Distributed exact weighted all-pairs shortest paths in near-linear time. - Aaron Bernstein; Danupon Nanongkai (STOC, 2019)

Distributed edge connectivity in sublinear time. - Mohit Daga; Monika Henzinger; Danupon Nanongkai; Thatchaphol Saranurak (STOC, 2019)

Breaking quadratic time for small vertex connectivity and an approximation scheme. - Danupon Nanongkai; Thatchaphol Saranurak; Sorrachai Yingchareonthawornchai (STOC, 2019)

New Tools and Connections for Exponential-Time Approximation. - Nikhil Bansal 001; Parinya Chalermsook; Bundit Laekhanukit; Danupon Nanongkai; Jesper Nederlof (Algorithmica, 2019)

Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries. - Danupon Nanongkai; Thatchaphol Saranurak; Sorrachai Yingchareonthawornchai (CoRR, 2019)

Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex. - Yu Gao 001; Jason Li 006; Danupon Nanongkai; Richard Peng; Thatchaphol Saranurak; Sorrachai Yingchareonthawornchai (CoRR, 2019)

Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time. - Aaron Bernstein; Danupon Nanongkai (SIAM J. Comput., 2019)

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. - Jan van den Brand; Yin Tat Lee; Danupon Nanongkai; Richard Peng; Thatchaphol Saranurak; Aaron Sidford; Zhao Song 002; Di Wang 005 (FOCS, 2020)

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. - Julia Chuzhoy; Yu Gao 001; Jason Li 006; Danupon Nanongkai; Richard Peng; Thatchaphol Saranurak (FOCS, 2020)

Coarse-Grained Complexity for Dynamic Algorithms. - Sayan Bhattacharya; Danupon Nanongkai; Thatchaphol Saranurak (SODA, 2020)

Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms. - Sebastian Forster; Danupon Nanongkai; Liu Yang; Thatchaphol Saranurak; Sorrachai Yingchareonthawornchai (SODA, 2020)

Weighted min-cut: sequential, cut-query, and streaming algorithms. - Sagnik Mukhopadhyay; Danupon Nanongkai (STOC, 2020)

An Improved Algorithm for Dynamic Set Cover. - Sayan Bhattacharya; Monika Henzinger; Danupon Nanongkai; Xiaowei Wu 001 (CoRR, 2020)

From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More. - Parinya Chalermsook; Marek Cygan; Guy Kortsarz; Bundit Laekhanukit; Pasin Manurangsi; Danupon Nanongkai; Luca Trevisan 001 (SIAM J. Comput., 2020)

Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018). - Thomas Vidick; Danupon Nanongkai; Dimitris Achlioptas (SIAM J. Comput., 2020)

Minimum Cuts in Directed Graphs via Partial Sparsification. - Ruoxu Cen; Jason Li 006; Danupon Nanongkai; Debmalya Panigrahi; Thatchaphol Saranurak; Kent Quanrud (FOCS, 2021)

Dynamic Set Cover: Improved Amortized and Worst-Case Update Time. - Sayan Bhattacharya; Monika Henzinger; Danupon Nanongkai; Xiaowei Wu 001 (SODA, 2021)

Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs. - Andrés López-Martínez; Sagnik Mukhopadhyay; Danupon Nanongkai (SPAA, 2021)

Breaking the quadratic barrier for matroid intersection. - Joakim Blikstad; Jan van den Brand; Sagnik Mukhopadhyay; Danupon Nanongkai (STOC, 2021)

Distributed weighted min-cut in nearly-optimal time. - Michal Dory; Yuval Efron; Sagnik Mukhopadhyay; Danupon Nanongkai (STOC, 2021)

A Note on Isolating Cut Lemma for Submodular Function Minimization. - Sagnik Mukhopadhyay; Danupon Nanongkai (CoRR, 2021)

Minimum Cuts in Directed Graphs via √n Max-Flows. - Ruoxu Cen; Jason Li 006; Danupon Nanongkai; Debmalya Panigrahi; Thatchaphol Saranurak (CoRR, 2021)

A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths. - Monika Henzinger; Sebastian Krinninger; Danupon Nanongkai (SIAM J. Comput., 2021)

Cut Query Algorithms with Star Contraction. - Simon Apers; Yuval Efron; Pawel Gawrychowski; Troy Lee; Sagnik Mukhopadhyay; Danupon Nanongkai (FOCS, 2022)

Nearly Optimal Communication and Query Complexity of Bipartite Matching. - Joakim Blikstad; Jan van den Brand; Yuval Efron; Sagnik Mukhopadhyay; Danupon Nanongkai (FOCS, 2022)

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. - Aaron Bernstein; Jan van den Brand; Maximilian Probst Gutenberg; Danupon Nanongkai; Thatchaphol Saranurak; Aaron Sidford; He Sun 001 (ICALP, 2022)

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. - Parinya Chalermsook; Chien-Chung Huang 001; Danupon Nanongkai; Thatchaphol Saranurak; Pattara Sukprasert; Sorrachai Yingchareonthawornchai (ICALP, 2022)

Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition. - Calvin Beideman; Karthekeyan Chandrasekaran; Sagnik Mukhopadhyay; Danupon Nanongkai (IPCO, 2022)

Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time. - Jason Li 006; Danupon Nanongkai; Debmalya Panigrahi; Thatchaphol Saranurak (CoRR, 2022)

Negative-Weight Single-Source Shortest Paths in Almost-linear Time. - Aaron Bernstein; Danupon Nanongkai; Christian Wulff-Nilsen (CoRR, 2022)

Equivalence classes and conditional hardness in massively parallel computations. - Danupon Nanongkai; Michele Scquizzato (Distributed Comput., 2022)

Near-Linear Time Approximations for Cut Problems via Fair Cuts. - Jason Li 006; Danupon Nanongkai; Debmalya Panigrahi; Thatchaphol Saranurak (SODA, 2023)

Fully Dynamic Exact Edge Connectivity in Sublinear Time. - Gramoz Goranci; Monika Henzinger; Danupon Nanongkai; Thatchaphol Saranurak; Mikkel Thorup; Christian Wulff-Nilsen (SODA, 2023)

Fast Algorithms via Dynamic-Oracle Matroids. - Joakim Blikstad; Sagnik Mukhopadhyay; Danupon Nanongkai; Ta-Wei Tu (STOC, 2023)

Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights. - Vikrant Ashvinkumar; Aaron Bernstein; Nairen Cao; Christoph Grunau; Bernhard Haeupler; Yonggang Jiang; Danupon Nanongkai; Hsin-Hao Su (CoRR, 2023)

Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover. - Sayan Bhattacharya; Monika Henzinger; Danupon Nanongkai; Xiaowei Wu 001 (SIAM J. Comput., 2023)

Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights. - Vikrant Ashvinkumar; Aaron Bernstein; Nairen Cao; Christoph Grunau; Bernhard Haeupler; Yonggang Jiang; Danupon Nanongkai; Hsin-Hao Su (ESA, 2024)

Cross-Paradigm Graph Algorithms (Invited Talk). - Danupon Nanongkai (ICALP, 2024)

Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions. - Martin G. Herold; Danupon Nanongkai; Joachim Spoerhase; Nithin Varma 001; Zihang Wu (SoCG, 2025)

Negative-Weight Single-Source Shortest Paths in Near-Linear Time. - Aaron Bernstein; Danupon Nanongkai; Christian Wulff-Nilsen (Commun. ACM, 2025)

Shortcuts and Transitive-Closure Spanners Approximation. - Parinya Chalermsook; Yonggang Jiang; Sagnik Mukhopadhyay; Danupon Nanongkai (CoRR, 2025)

Vertex Connectivity in Poly-logarithmic Max-Flows. - Jason Li 006; Danupon Nanongkai; Debmalya Panigrahi; Thatchaphol Saranurak; Sorrachai Yingchareonthawornchai (J. ACM, 2025)