Danupon Nanongkai
Danupon Nanongkai
Professor, University of Copenhagen, Denmark
Verified email at di.ku.dk - Homepage
Title
Cited by
Cited by
Year
Distributed verification and hardness of distributed approximation
A Das Sarma, S Holzer, L Kor, A Korman, D Nanongkai, G Pandurangan, ...
SIAM Journal on Computing, 2012
2872012
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
M Henzinger, S Krinninger, D Nanongkai, T Saranurak
Proceedings of the forty-seventh annual ACM symposium on Theory of computing …, 2015
1962015
Distributed approximation algorithms for weighted shortest paths
D Nanongkai
Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014
1472014
Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams
S Bhattacharya, M Henzinger, D Nanongkai, C Tsourakakis
Proceedings of the forty-seventh annual ACM symposium on Theory of computing …, 2015
1022015
Regret-minimizing representative databases
D Nanongkai, AD Sarma, A Lall, RJ Lipton, J Xu
Proceedings of the VLDB Endowment 3 (1-2), 1114-1124, 2010
1012010
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
M Henzinger, S Krinninger, D Nanongkai
SIAM Journal on Computing, STOC16-98-STOC16-137, 2019
912019
Decremental single-source shortest paths on undirected graphs in near-linear total update time
M Henzinger, S Krinninger, D Nanongkai
2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 146-155, 2014
832014
Dynamic minimum spanning forest with subpolynomial worst-case update time
D Nanongkai, T Saranurak, C Wulff-Nilsen
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017
822017
Distributed Computation of Large-scale Graph Problems
H Klauck, D Nanongkai, PR Gopal Pandurangan
ACM-SIAM Symposium on Discrete Algorithms, 391-410, 2015
822015
Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization
M Henzinger, S Krinninger, D Nanongkai
Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on …, 2013
762013
From gap-eth to fpt-inapproximability: Clique, dominating set, and more
P Chalermsook, M Cygan, G Kortsarz, B Laekhanukit, P Manurangsi, ...
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017
742017
Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time
D Nanongkai, T Saranurak
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017
702017
New deterministic approximation algorithms for fully dynamic matching
S Bhattacharya, M Henzinger, D Nanongkai
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing …, 2016
682016
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time
S Bhattacharya, M Henzinger, D Nanongkai
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete …, 2017
602017
Independent set, induced matching, and pricing: Connections and tight (subexponential time) approximation hardnesses
P Chalermsook, B Laekhanukit, D Nanongkai
2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 370-379, 2013
602013
Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
M Henzinger, S Krinninger, D Nanongkai
Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014
582014
Graph products revisited: Tight approximation hardness of induced matching, poset dimension and more
P Chalermsook, B Laekhanukit, D Nanongkai
Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete …, 2013
572013
Randomized multi-pass streaming skyline algorithms
A Das Sarma, A Lall, D Nanongkai, J Xu
Proceedings of the VLDB Endowment 2 (1), 85-96, 2009
572009
Distributed random walks
A Das Sarma, D Nanongkai, G Pandurangan, P Tetali
Journal of the ACM (JACM) 60 (1), 2, 2013
562013
Representative skylines using threshold-based preference distributions
A Das Sarma, A Lall, D Nanongkai, RJ Lipton, J Xu
Data Engineering (ICDE), 2011 IEEE 27th International Conference on, 387-398, 2011
552011
The system can't perform the operation now. Try again later.
Articles 1–20