Danupon Nanongkai

169 papers A* 58A 5B 4C 1Journal 94Unranked 5
YearRankTypeTitle / Venue / Authors
2026 A* conf
Minimum
SODA
Yonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya
2026 A* conf
Shortcuts and Transitive-Closure Spanners Approximation.
SODA
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai
2025 J jnl
Minimum s-t Cuts with Fewer Cut Queries.
CoRR
Yonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya
2025 J jnl
Negative-Weight Single-Source Shortest Paths in Near-Linear Time.
Commun. ACM
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
2025 J jnl
Negative-Weight Single-Source Shortest Paths in Near-linear Time.
J. ACM
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
2025 J jnl
Shortcuts and Transitive-Closure Spanners Approximation.
CoRR
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai
2025 A* conf
Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions.
SoCG
Martin G. Herold, Danupon Nanongkai, Joachim Spoerhase, Nithin Varma, Zihang Wu
2025 J jnl
Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions.
CoRR
Martin G. Herold, Danupon Nanongkai, Joachim Spoerhase, Nithin Varma, Zihang Wu
2025 J jnl
Vertex Connectivity in Poly-logarithmic Max-Flows.
J. ACM
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
2024 A* conf
Cross-Paradigm Graph Algorithms (Invited Talk).
ICALP
Danupon Nanongkai
2024 A conf
Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights.
ESA
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin-Hao Su
2023 J jnl
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.
SIAM J. Comput.
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu
2023 A* conf
Fast Algorithms via Dynamic-Oracle Matroids.
STOC
Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, Ta-Wei Tu
2023 J jnl
Fast Algorithms via Dynamic-Oracle Matroids.
CoRR
Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, Ta-Wei Tu
2023 A* conf
Fully Dynamic Exact Edge Connectivity in Sublinear Time.
SODA
Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen
2023 J jnl
Fully Dynamic Exact Edge Connectivity in Sublinear Time.
CoRR
Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen
2023 A* conf
Near-Linear Time Approximations for Cut Problems via Fair Cuts.
SODA
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak
2023 J jnl
Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights.
CoRR
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin-Hao Su
2022 A* conf
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver.
ICALP
Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, Sorrachai Yingchareonthawornchai
2022 J jnl
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver.
CoRR
Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, Sorrachai Yingchareonthawornchai
2022 A* conf
Cut Query Algorithms with Star Contraction.
FOCS
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
2022 J jnl
Cut query algorithms with star contraction.
CoRR
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
2022 J jnl
Equivalence classes and conditional hardness in massively parallel computations.
Distributed Comput.
Danupon Nanongkai, Michele Scquizzato
2022 J jnl
Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time.
CoRR
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak
2022 B conf
Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition.
IPCO
Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai
2022 A* conf
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.
ICALP
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
2022 A* conf
Nearly Optimal Communication and Query Complexity of Bipartite Matching.
FOCS
Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
2022 J jnl
Nearly Optimal Communication and Query Complexity of Bipartite Matching.
CoRR
Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
2022 J jnl
Negative-Weight Single-Source Shortest Paths in Almost-linear Time.
CoRR
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
2022 A* conf
Negative-Weight Single-Source Shortest Paths in Near-linear Time.
FOCS
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
2021 J jnl
A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.
SIAM J. Comput.
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2021 J jnl
A Note on Isolating Cut Lemma for Submodular Function Minimization.
CoRR
Sagnik Mukhopadhyay, Danupon Nanongkai
2021 J jnl
Breaking the Quadratic Barrier for Matroid Intersection.
CoRR
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai
2021 A* conf
Breaking the quadratic barrier for matroid intersection.
STOC
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai
2021 A* conf
Distributed weighted min-cut in nearly-optimal time.
STOC
Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
2021 A* conf
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.
SODA
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu
2021 A* conf
Minimum Cuts in Directed Graphs via Partial Sparsification.
FOCS
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Kent Quanrud
2021 J jnl
Minimum Cuts in Directed Graphs via Partial Sparsification.
CoRR
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Kent Quanrud, Thatchaphol Saranurak
2021 J jnl
Minimum Cuts in Directed Graphs via √n Max-Flows.
CoRR
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak
2021 J jnl
Vertex Connectivity in Poly-logarithmic Max-flows.
CoRR
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
2021 A* conf
Vertex connectivity in poly-logarithmic max-flows.
STOC
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
2021 B conf
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs.
SPAA
Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai
2021 J jnl
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs.
CoRR
Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai
2020 A* conf
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond.
FOCS
Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak
2020 J jnl
An Improved Algorithm for Dynamic Set Cover.
CoRR
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu
2020 A* conf
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.
FOCS
Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
2020 J jnl
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.
CoRR
Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
2020 A* conf
Coarse-Grained Complexity for Dynamic Algorithms.
SODA
Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
2020 J jnl
Coarse-Grained Complexity for Dynamic Algorithms.
CoRR
Sayan Bhattacharya, Danupon Nanongkai, Thatchaphol Saranurak
2020 A* conf
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms.
SODA
Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
2020 J jnl
Distributed Weighted Min-Cut in Nearly-Optimal Time.
CoRR
Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
2020 J jnl
Equivalence Classes and Conditional Hardness in Massively Parallel Computations.
CoRR
Danupon Nanongkai, Michele Scquizzato
2020 J jnl
Faster connectivity in low-rank hypergraphs via expander decomposition.
CoRR
Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai
2020 J jnl
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More.
SIAM J. Comput.
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2020 J jnl
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.
CoRR
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
2020 J jnl
Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018).
SIAM J. Comput.
Thomas Vidick, Danupon Nanongkai, Dimitris Achlioptas
2020 A* conf
Weighted min-cut: sequential, cut-query, and streaming algorithms.
STOC
Sagnik Mukhopadhyay, Danupon Nanongkai
2019 J jnl
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond.
CoRR
Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak
2019 A* conf
A New Deterministic Algorithm for Dynamic Set Cover.
FOCS
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2019 J jnl
A New Deterministic Algorithm for Dynamic Set Cover.
CoRR
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2019 J jnl
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme.
CoRR
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
2019 A* conf
Breaking quadratic time for small vertex connectivity and an approximation scheme.
STOC
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
2019 J jnl
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms.
CoRR
Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak, Liu Yang, Sorrachai Yingchareonthawornchai
2019 J jnl
Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries.
CoRR
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
2019 J jnl
Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex.
CoRR
Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
2019 J jnl
Distributed Edge Connectivity in Sublinear Time.
CoRR
Mohit Daga, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak
2019 J jnl
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time.
SIAM J. Comput.
Aaron Bernstein, Danupon Nanongkai
2019 A* conf
Distributed edge connectivity in sublinear time.
STOC
Mohit Daga, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak
2019 A* conf
Distributed exact weighted all-pairs shortest paths in near-linear time.
STOC
Aaron Bernstein, Danupon Nanongkai
2019 A* conf
Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time.
FOCS
Jan van den Brand, Danupon Nanongkai
2019 J jnl
Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time.
CoRR
Jan van den Brand, Danupon Nanongkai
2019 A* conf
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds.
FOCS
Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak
2019 J jnl
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds.
CoRR
Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak
2019 B conf
Equivalence Classes and Conditional Hardness in Massively Parallel Computations.
OPODIS
Danupon Nanongkai, Michele Scquizzato
2019 J jnl
New Tools and Connections for Exponential-Time Approximation.
Algorithmica
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof
2019 J jnl
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms.
CoRR
Sagnik Mukhopadhyay, Danupon Nanongkai
2018 A* conf
A Faster Distributed Single-Source Shortest Paths Algorithm.
FOCS
Sebastian Forster, Danupon Nanongkai
2018 J jnl
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time.
J. ACM
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2018 J jnl
Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time.
CoRR
Aaron Bernstein, Danupon Nanongkai
2018 A* conf
Dynamic Algorithms for Graph Coloring.
SODA
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, Danupon Nanongkai
2017 J jnl
A Faster Distributed Single-Source Shortest Paths Algorithm.
CoRR
Sebastian Krinninger, Danupon Nanongkai
2017 J jnl
Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n
CoRR
Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak
2017 A* conf
Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n
FOCS
Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak
2017 J jnl
Dynamic Algorithms for Graph Coloring.
CoRR
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, Danupon Nanongkai
2017 A* conf
Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time.
FOCS
Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen
2017 J jnl
Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time.
CoRR
Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen
2017 A* conf
Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n
STOC
Danupon Nanongkai, Thatchaphol Saranurak
2017 A* conf
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.
FOCS
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2017 J jnl
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.
CoRR
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2017 A* conf
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in
SODA
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2017 J jnl
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log
CoRR
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2017 J jnl
New Tools and Connections for Exponential-time Approximation.
CoRR
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof
2017 J jnl
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.
ACM Trans. Algorithms
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2016 A* conf
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths.
STOC
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2016 J jnl
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.
SIAM J. Comput.
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2016 — ch.
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrierand Derandomization.
Encyclopedia of Algorithms
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2016 J jnl
Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and $O(n^{1/2-ε})$-Time.
CoRR
Danupon Nanongkai, Thatchaphol Saranurak
2016 J jnl
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.
CoRR
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2016 J jnl
New Deterministic Approximation Algorithms for Fully Dynamic Matching.
CoRR
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2016 A* conf
New deterministic approximation algorithms for fully dynamic matching.
STOC
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
2016 J jnl
Polynomial-Time Algorithms for Energy Games with Special Weight Structures.
CoRR
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2015 J jnl
An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths.
CoRR
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2015 J jnl
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time.
CoRR
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2015 A* conf
Distributed Computation of Large-scale Graph Problems.
SODA
Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson
2015 — conf
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.
ICALP (1)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2015 A* conf
Social Network Monetization via Sponsored Viral Marketing.
SIGMETRICS
Parinya Chalermsook, Atish Das Sarma, Ashwin Lall, Danupon Nanongkai
2015 A* conf
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.
STOC
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Charalampos E. Tsourakakis
2015 J jnl
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.
CoRR
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Charalampos E. Tsourakakis
2015 J jnl
Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs.
CoRR
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2015 J jnl
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.
CoRR
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2015 A* conf
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.
STOC
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak
2015 J jnl
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.
CoRR
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak
2014 A* conf
A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths.
SODA
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2014 A conf
Almost-Tight Distributed Minimum Cut Algorithms.
DISC
Danupon Nanongkai, Hsin-Hao Su
2014 J jnl
Almost-Tight Distributed Minimum Cut Algorithms.
CoRR
Danupon Nanongkai, Hsin-Hao Su
2014 J jnl
Brief Announcement: Almost-Tight Approximation Distributed Algorithm for Minimum Cut.
CoRR
Danupon Nanongkai
2014 A* conf
Brief announcement: almost-tight approximation distributed algorithm for minimum cut.
PODC
Danupon Nanongkai
2014 A* conf
Can quantum communication speed up distributed computation?
PODC
Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan
2014 B conf
Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation.
LATIN
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2014 A* conf
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time.
FOCS
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2014 J jnl
Distributed Approximation Algorithms for Weighted Shortest Paths.
CoRR
Danupon Nanongkai
2014 A conf
Distributed Symmetry Breaking in Hypergraphs.
DISC
Shay Kutten, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson
2014 J jnl
Distributed Symmetry Breaking in Hypergraphs.
CoRR
Shay Kutten, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson
2014 A* conf
Distributed approximation algorithms for weighted shortest paths.
STOC
Danupon Nanongkai
2014 J jnl
Faster Algorithms for Semi-Matching Problems.
ACM Trans. Algorithms
Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai
2014 J jnl
Polynomial-Time Algorithms for Energy Games with Special Weight Structures.
Algorithmica
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2014 J jnl
Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs.
CoRR
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2014 A* conf
Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs.
FOCS
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2014 A* conf
Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs.
STOC
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2013 J jnl
An Approximate Restatement of the Four-Color Theorem.
J. Graph Algorithms Appl.
Atish Das Sarma, Amita Gajewar, Richard J. Lipton, Danupon Nanongkai
2013 J jnl
Distributed Random Walks
CoRR
Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali
2013 J jnl
Distributed Random Walks.
J. ACM
Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali
2013 A* conf
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.
FOCS
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2013 J jnl
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.
CoRR
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2013 J jnl
Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs.
Chic. J. Theor. Comput. Sci.
Parinya Chalermsook, Shiva Kintali, Richard J. Lipton, Danupon Nanongkai
2013 A* conf
Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More.
SODA
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2013 A* conf
Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses.
FOCS
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2013 J jnl
Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses.
CoRR
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2013 J jnl
Simple FPTAS for the subset-sums ratio problem.
Inf. Process. Lett.
Danupon Nanongkai
2013 — conf
Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.
ICALP (2)
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2013 J jnl
The Distributed Complexity of Large-scale Graph Processing.
CoRR
Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson
2012 A* conf
Brief announcement: maintaining large dense subgraphs on dynamic networks.
PODC
Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Amitabh Trehan
2012 J jnl
Dense Subgraphs on Dynamic Networks
CoRR
Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Amitabh Trehan
2012 A conf
Dense Subgraphs on Dynamic Networks.
DISC
Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Amitabh Trehan
2012 J jnl
Distributed Verification and Hardness of Distributed Approximation.
SIAM J. Comput.
Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer
2012 J jnl
Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs
CoRR
Parinya Chalermsook, Shiva Kintali, Richard J. Lipton, Danupon Nanongkai
2012 J jnl
Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More
CoRR
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2012 — conf
Interactive regret minimization.
SIGMOD Conference
Danupon Nanongkai, Ashwin Lall, Atish Das Sarma, Kazuhisa Makino
2012 J jnl
Multi-Attribute Profit-Maximizing Pricing (Extended Abstract)
CoRR
Parinya Chalermsook, Khaled M. Elbassioni, Danupon Nanongkai, He Sun
2012 A conf
Polynomial-Time Algorithms for Energy Games with Special Weight Structures.
ESA
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
2012 J jnl
Quantum Distributed Network Computing: Lower Bounds and Techniques
CoRR
Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan
2011 J jnl
A Tight Lower Bound on Distributed Random Walk Computation
CoRR
Danupon Nanongkai, Atish Das Sarma, Gopal Pandurangan
2011 A* conf
A tight unconditional lower bound on distributed randomwalk computation.
PODC
Danupon Nanongkai, Atish Das Sarma, Gopal Pandurangan
2011 J jnl
Best-order streaming model.
Theor. Comput. Sci.
Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai
2011 A* conf
Distributed verification and hardness of distributed approximation.
STOC
Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer
2011 — —
Graph and geometric algorithms on distributed networks and databases.
Danupon Nanongkai
2011 A* conf
Representative skylines using threshold-based preference distributions.
ICDE
Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Richard J. Lipton, Jun (Jim) Xu
2010 J jnl
Distributed Verification and Hardness of Distributed Approximation
CoRR
Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer
2010 A* conf
Efficient distributed random walks with applications.
PODC
Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali
2010 J jnl
Faster Algorithms for Semi-Matching Problems
CoRR
Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai
2010 — conf
Faster Algorithms for Semi-matching Problems (Extended Abstract).
ICALP (1)
Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai
2010 — conf
Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing.
WINE
Patrick Briest, Parinya Chalermsook, Sanjeev Khanna, Bundit Laekhanukit, Danupon Nanongkai
2010 J jnl
Regret-Minimizing Representative Databases.
Proc. VLDB Endow.
Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Richard J. Lipton, Jun (Jim) Xu
2009 C conf
Best-Order Streaming Model.
TAMC
Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai
2009 A* conf
Fast distributed random walks.
PODC
Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan
2009 J jnl
Near-Optimal Sublinear Time Bounds for Distributed Random Walks
CoRR
Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali
2009 J jnl
Randomized Multi-pass Streaming Skyline Algorithms.
Proc. VLDB Endow.
Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Jun (Jim) Xu
2009 J jnl
Stackelberg Pricing is Hard to Approximate within 2-ε
CoRR
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
2004 A* conf
A deterministic near-linear time algorithm for finding minimum cuts in planar graphs.
SODA
Parinya Chalermsook, Jittat Fakcharoenphol, Danupon Nanongkai