Danupon Nanongkai

ORCID

Publication Activity (10 Years)

Years Active: 2004-2024
Publications (10 Years): 90

Top Venues

Publications

Danupon Nanongkai
Cross-Paradigm Graph Algorithms (Invited Talk). ICALP (2024)
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak
Near-Linear Time Approximations for Cut Problems via Fair Cuts. SODA (2023)
Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen
Fully Dynamic Exact Edge Connectivity in Sublinear Time. SODA (2023)
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover. SIAM J. Comput. 52 (5) (2023)
Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, Ta-Wei Tu
Fast Algorithms via Dynamic-Oracle Matroids. STOC (2023)
Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen
Fully Dynamic Exact Edge Connectivity in Sublinear Time. CoRR (2023)
Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, Ta-Wei Tu
Fast Algorithms via Dynamic-Oracle Matroids. CoRR (2023)
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin-Hao Su
Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights. CoRR (2023)
Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
Nearly Optimal Communication and Query Complexity of Bipartite Matching. FOCS (2022)
Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, Sorrachai Yingchareonthawornchai
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. CoRR (2022)
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. ICALP (2022)
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Kent Quanrud
Minimum Cuts in Directed Graphs via Partial Sparsification. FOCS (2022)
Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai
Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition. IPCO (2022)
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
Cut query algorithms with star contraction. CoRR (2022)
Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, Sorrachai Yingchareonthawornchai
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. ICALP (2022)
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
Cut Query Algorithms with Star Contraction. FOCS (2022)
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak
Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time. CoRR (2022)
Danupon Nanongkai, Michele Scquizzato
Equivalence classes and conditional hardness in massively parallel computations. Distributed Comput. 35 (2) (2022)
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
Negative-Weight Single-Source Shortest Paths in Almost-linear Time. CoRR (2022)
Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
Nearly Optimal Communication and Query Complexity of Bipartite Matching. CoRR (2022)
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
Negative-Weight Single-Source Shortest Paths in Near-linear Time. FOCS (2022)
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai
Breaking the Quadratic Barrier for Matroid Intersection. CoRR (2021)
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
Vertex Connectivity in Poly-logarithmic Max-flows. CoRR (2021)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths. SIAM J. Comput. 50 (3) (2021)
Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs. CoRR (2021)
Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
Distributed weighted min-cut in nearly-optimal time. STOC (2021)
Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs. SPAA (2021)
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Kent Quanrud, Thatchaphol Saranurak
Minimum Cuts in Directed Graphs via Partial Sparsification. CoRR (2021)
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai
Breaking the quadratic barrier for matroid intersection. STOC (2021)
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
Vertex connectivity in poly-logarithmic max-flows. STOC (2021)
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Kent Quanrud
Minimum Cuts in Directed Graphs via Partial Sparsification. FOCS (2021)
Sagnik Mukhopadhyay, Danupon Nanongkai
A Note on Isolating Cut Lemma for Submodular Function Minimization. CoRR (2021)
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak
Minimum Cuts in Directed Graphs via √n Max-Flows. CoRR (2021)
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time. SODA (2021)
Sagnik Mukhopadhyay, Danupon Nanongkai
Weighted min-cut: sequential, cut-query, and streaming algorithms. STOC (2020)
Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. CoRR (2020)
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More. SIAM J. Comput. 49 (4) (2020)
Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms. SODA (2020)
Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
Coarse-Grained Complexity for Dynamic Algorithms. CoRR (2020)
Danupon Nanongkai, Michele Scquizzato
Equivalence Classes and Conditional Hardness in Massively Parallel Computations. CoRR (2020)
Thomas Vidick, Danupon Nanongkai, Dimitris Achlioptas
Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018). SIAM J. Comput. 49 (5) (2020)
Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. FOCS (2020)
Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai
Faster connectivity in low-rank hypergraphs via expander decomposition. CoRR (2020)
Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. FOCS (2020)
Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
Distributed Weighted Min-Cut in Nearly-Optimal Time. CoRR (2020)
Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
Coarse-Grained Complexity for Dynamic Algorithms. SODA (2020)
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. CoRR (2020)
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu
An Improved Algorithm for Dynamic Set Cover. CoRR (2020)
Danupon Nanongkai, Michele Scquizzato
Equivalence Classes and Conditional Hardness in Massively Parallel Computations. OPODIS (2019)
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme. CoRR (2019)
Mohit Daga, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak
Distributed edge connectivity in sublinear time. STOC (2019)
Jan van den Brand, Danupon Nanongkai
Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time. CoRR (2019)
Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak, Liu Yang, Sorrachai Yingchareonthawornchai
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms. CoRR (2019)
Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. CoRR (2019)
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
A New Deterministic Algorithm for Dynamic Set Cover. FOCS (2019)
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
Breaking quadratic time for small vertex connectivity and an approximation scheme. STOC (2019)
Sagnik Mukhopadhyay, Danupon Nanongkai
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms. CoRR (2019)
Aaron Bernstein, Danupon Nanongkai
Distributed exact weighted all-pairs shortest paths in near-linear time. STOC (2019)
Mohit Daga, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak
Distributed Edge Connectivity in Sublinear Time. CoRR (2019)
Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. FOCS (2019)
Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex. CoRR (2019)
Jan van den Brand, Danupon Nanongkai
Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time. FOCS (2019)
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
A New Deterministic Algorithm for Dynamic Set Cover. CoRR (2019)
Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. CoRR (2019)
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof
New Tools and Connections for Exponential-Time Approximation. Algorithmica 81 (10) (2019)
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries. CoRR (2019)
Aaron Bernstein, Danupon Nanongkai
Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time. CoRR (2018)
Sebastian Forster, Danupon Nanongkai
A Faster Distributed Single-Source Shortest Paths Algorithm. FOCS (2018)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. J. ACM 65 (6) (2018)
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, Danupon Nanongkai
Dynamic Algorithms for Graph Coloring. SODA (2018)
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
n) Worst Case Update Time. CoRR (2017)
Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak
) Rounds. FOCS (2017)
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. FOCS (2017)
Sebastian Krinninger, Danupon Nanongkai
A Faster Distributed Single-Source Shortest Paths Algorithm. CoRR (2017)
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
) Worst Case Update Time. SODA (2017)
Danupon Nanongkai, Thatchaphol Saranurak
)-time. STOC (2017)
Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen
Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time. CoRR (2017)
Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak
) Rounds. CoRR (2017)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks. ACM Trans. Algorithms 13 (4) (2017)
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. CoRR (2017)
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof
New Tools and Connections for Exponential-time Approximation. CoRR (2017)
Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen
Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. FOCS (2017)
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, Danupon Nanongkai
Dynamic Algorithms for Graph Coloring. CoRR (2017)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization. SIAM J. Comput. 45 (3) (2016)
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
New deterministic approximation algorithms for fully dynamic matching. STOC (2016)
Danupon Nanongkai, Thatchaphol Saranurak
Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and $O(n^{1/2-ε})$-Time. CoRR (2016)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs. CoRR (2016)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. STOC (2016)
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
New Deterministic Approximation Algorithms for Fully Dynamic Matching. CoRR (2016)
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
Polynomial-Time Algorithms for Energy Games with Special Weight Structures. CoRR (2016)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. STOC (2015)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs. CoRR (2015)
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Charalampos E. Tsourakakis
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. CoRR (2015)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths. CoRR (2015)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks. CoRR (2015)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. CoRR (2015)
Parinya Chalermsook, Atish Das Sarma, Ashwin Lall, Danupon Nanongkai
Social Network Monetization via Sponsored Viral Marketing. SIGMETRICS (2015)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. CoRR (2015)
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Charalampos E. Tsourakakis
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. STOC (2015)
Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson
Distributed Computation of Large-scale Graph Problems. SODA (2015)

Danupon Nanongkai.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Danupon Nanongkai