Danupon Nanongkai

Available identifiers

zbMath Open nanongkai.danuponWikidataQ102389794 ScholiaQ102389794MaRDI QIDQ487010

List of research outcomes

Publication	Date of Publication	Type
https://portal.mardi4nfdi.de/entity/Q6147407	2024-01-15	Paper
Distributed weighted min-cut in nearly-optimal time	2023-11-14	Paper
Vertex connectivity in poly-logarithmic max-flows	2023-11-14	Paper
Breaking the quadratic barrier for matroid intersection	2023-11-14	Paper
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover	2023-10-26	Paper
Equivalence classes and conditional hardness in massively parallel computations	2023-02-07	Paper
Faster connectivity in low-rank hypergraphs via expander decomposition	2022-08-16	Paper
Equivalence classes and conditional hardness in massively parallel computations	2022-04-01	Paper
Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time	2022-01-07	Paper
A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths	2021-06-29	Paper
Coarse-Grained Complexity for Dynamic Algorithms	2021-02-02	Paper
Weighted min-cut: sequential, cut-query, and streaming algorithms	2021-01-19	Paper
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More	2020-08-18	Paper
Breaking quadratic time for small vertex connectivity and an approximation scheme	2020-01-30	Paper
Distributed exact weighted all-pairs shortest paths in near-linear time	2020-01-30	Paper
Distributed edge connectivity in sublinear time	2020-01-30	Paper
New tools and connections for exponential-time approximation	2019-09-10	Paper
A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths	2019-06-20	Paper
Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation	2019-05-15	Paper
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time	2019-02-25	Paper
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks	2018-11-12	Paper
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time	2018-07-16	Paper
https://portal.mardi4nfdi.de/entity/Q4607872	2018-03-15	Paper
Distributed Computation of Large-scale Graph Problems	2017-10-05	Paper
New deterministic approximation algorithms for fully dynamic matching	2017-09-29	Paper
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths	2017-09-29	Paper
Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time	2017-08-17	Paper
Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization	2016-07-04	Paper
Faster Algorithms for Semi-Matching Problems	2016-04-11	Paper
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs	2015-10-27	Paper
A tight unconditional lower bound on distributed randomwalk computation	2015-09-11	Paper
Can quantum communication speed up distributed computation?	2015-09-03	Paper
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture	2015-08-21	Paper
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams	2015-08-21	Paper
https://portal.mardi4nfdi.de/entity/Q5501344	2015-08-03	Paper
Distributed approximation algorithms for weighted shortest paths	2015-06-26	Paper
Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs	2015-06-26	Paper
Efficient distributed random walks with applications	2015-03-02	Paper
Almost-Tight Distributed Minimum Cut Algorithms	2015-02-10	Paper
Polynomial-time algorithms for energy games with special weight structures	2015-01-19	Paper
Brief announcement	2014-12-05	Paper
Fast distributed random walks	2014-07-23	Paper
Distributed verification and hardness of distributed approximation	2014-06-05	Paper
https://portal.mardi4nfdi.de/entity/Q5414632	2014-05-07	Paper
Simple FPTAS for the subset-sums ratio problem	2014-04-14	Paper
Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation	2014-03-31	Paper
Distributed Random Walks	2014-02-17	Paper
An Approximate Restatement of the Four-Color Theorem	2013-10-29	Paper
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks	2013-08-07	Paper
Dense Subgraphs on Dynamic Networks	2013-03-13	Paper
Distributed Verification and Hardness of Distributed Approximation	2013-02-04	Paper
Polynomial-time algorithms for energy games with special weight structures	2012-09-25	Paper
Best-order streaming model	2011-05-18	Paper
Faster Algorithms for Semi-matching Problems (Extended Abstract)	2010-09-07	Paper
Best-Order Streaming Model	2009-06-03	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Danupon Nanongkai