Items where Author is "Nanongkai, Danupon"

Up a level
Export as [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0
Group by: Category | No Grouping
Jump to: Journal Paper | Paper in Conference Proceedings or in Workshop Proceedings | Book Section/Chapter
Number of items: 38.

Journal Paper

  • A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
    Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon ISSN 0097-5397 (2021)

  • Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
    Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon ISSN 0004-5411 (2018)

  • Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.
    Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon ISSN 1549-6325 (2017)

  • Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
    Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon pp. 947-1006 ISSN 0097-5397 (2016)

  • Faster Algorithms for Semi-Matching Problems
    Fakcharoenphol, Jittat and Laekhanukit, Bundit and Nanongkai, Danupon ACM Transactions on Algorithms, 10 (3). pp. 1-23 ISSN 1549-6325 (2014)

  • Polynomial-Time Algorithms for Energy Games with Special Weight Structures
    Chatterjee, Krishnendu and Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon pp. 457-492 ISSN 0178-4617 (2014)

  • An Approximate Restatement of the Four-Color Theorem
    Das Sarma, Atish and Gajewar, Amita and Lipton, Richard J. and Nanongkai, Danupon J. Graph Algorithms Appl., 17 (5). pp. 567-573 ISSN 1526-1719 (2013)

  • Distributed Random Walks
    Das Sarma, Atish and Nanongkai, Danupon and Pandurangan, Gopal and Tetali, Prasad J. ACM, 60 (1). p. 2 ISSN 0004-5411 (2013)

  • Simple FPTAS for the subset-sums ratio problem
    Nanongkai, Danupon Inf. Process. Lett., 113 (19-21). pp. 750-753 ISSN 0020-0190 (2013)

  • Distributed Verification and Hardness of Distributed Approximation
    Sarma, Atish Das and Holzer, Stephan and Kor, Liah and Korman, Amos and Nanongkai, Danupon and Pandurangan, Gopal and Peleg, David and Wattenhofer, Roger SIAM Journal on Computing (SICOMP), 41 (5). pp. 1235-1265 ISSN 0097-5397 Society for Industrial and Applied Mathematics (2012)

  • Best-Order Streaming model
    Das Sarma, Atish and Lipton, Richard J. and Nanongkai, Danupon Theoretical Computer Science, 412 (23). pp. 2544-2555 Elsevier (2011)

    • Paper in Conference Proceedings or in Workshop Proceedings

  • Fully Dynamic Exact Edge Connectivity in Sublinear Time
    Goranci, Gramoz and Henzinger, Monika and Nanongkai, Danupon and Saranurak, Thatchaphol and Thorup, Mikkel and Wulff-Nilsen, Christian In: ACM-SIAM Symposium on Discrete Algorithms (SODA23) , January 22 - 25, 2023 , Florence, Italy (2023)

  • Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
    Bhattacharya, Sayan and Henzinger, Monika and Nanongkai, Danupon and Wu, Xiaowei In: ACM-SIAM Symposium on Discrete Algorithms (SODA21) , 10.1.-13.1.2021 , Virtual Conference (2021)

  • A New Deterministic Algorithm for Dynamic Set Cover
    Bhattacharya, Sayan and Henzinger, Monika and Nanongkai, Danupon In: 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019) , November 9-12, 2019 , Baltimore, Maryland, USA (2019)

  • Distributed edge connectivity in sublinear time.
    Daga, Mohit and Henzinger, Monika and Nanongkai, Danupon and Saranurak, Thatchaphol In: 51st Annual ACM Symposium on the Theory of Computing , June 23-26, 2019 , Phoenix, AZ, USA (2019)

  • Dynamic Algorithms for Graph Coloring
    Bhattacharya, Sayan and Chakrabarty, Deeparnab and Henzinger, Monika and Nanongkai, Danupon In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018) , January 7-10, 2018 , New Orleans, LA, USA (2018)

  • Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log^3 n) Worst Case Update Time
    Bhattacharya, Sayan and Henzinger, Monika and Nanongkai, Danupon In: Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms 2017 , January 16-19, 2017 , Barcelona, Spain (2017)

  • A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
    Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon In: STOC 2016: 48th Annual Symposium on the Theory of Computing , 19-21 Jun 2016 , Cambridge, MA, USA (2016)

  • New Deterministic Approximation Algorithms for Fully Dynamic Matching
    Bhattacharya, Sayan and Henzinger, Monika and Nanongkai, Danupon In: STOC 2016: 48th Annual Symposium on the Theory of Computing , 19-21 Jun 2016 , Cambridge, MA, USA (2016)

  • Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
    Bhattacharya, Sayan and Henzinger, Monika and Nanongkai, Danupon and Tsourakakis, Charalampos E. In: 47th ACM Symposium on Theory of Computing (STOC 2015) , June 14 - June 17 , Portland, OR, USA (2015)

  • Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
    Henzinger, Monika and Nanongkai, Danupon and Krinninger, Sebastian In: 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015) , July 6–10, 2015 , Kyoto, Japan (2015)

  • Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
    Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon and Saranurak, Thatchaphol In: 47th ACM Symposium on Theory of Computing (STOC 2015) , June 14 - June 17 , Portland, OR, USA (2015)

  • Almost-Tight Distributed Minimum Cut Algorithms
    Nanongkai, Danupon and Su, Hsin-Hao In: 28th International Symposium on Distributed Computing 2014 , 12-15 October 2014 , Austin, Texas, USA (2014)

  • Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
    Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon In: 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014) , October 18-21, 2014 , Philadelphia, USA (2014)

  • Distributed Symmetry Breaking in Hypergraphs
    Kutten, Shay and Nanongkai, Danupon and Pandurangan, Gopal and Robinson, Peter In: 28th International Symposium on Distributed Computing 2014 , 12-15 October 2014 , Austin, Texas, USA (2014)

  • Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs
    Chalermsook, Parinya and Laekhanukit, Bundit and Nanongkai, Danupon In: 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014) , October 18-21, 2014 , Philadelphia, USA (2014)

  • Can Quantum Communication Speed Up Distributed Computation?
    Elkin, Michael and Klauck, Hartmut and Nanongkai, Danupon and Pandurangan, Gopal In: 33rd ACM Symposium on Principles of Distributed Computing (July 15th-18th 2014), hosted in Paris, France , July 15th - 18th 2014 , Paris, France (2014)

  • Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs
    Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon In: 46th ACM Symposium on Theory of Computing (STOC 2014) , June 1 – June 3, 2014 , New York, NY, USA (2014)

  • A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths
    Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon In: 25th ACM-SIAM Symposium on Discrete Algorithms (SODA14) , January 5-7, 2014 , Portland, USA (In Press) (2014)

  • Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
    Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon In: FOCS 2013 54th Annual IEEE Symposium on Foundations of Computer Science , October 27-29, 2013 , Berkeley, USA (In Press) (2013)

  • Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks
    Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon In: 40th International Colloquium on Automata, Languages and Programming (ICALP 2013) , 8-12 July 2013 , Riga, Latvia (In Press) (2013)

  • Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More
    Chalermsook, Parinya and Laekhanukit, Bundit and Nanongkai, Danupon In: 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013) , 6-8 Jan 2013 , New Orleans, USA (In Press) (2013)

  • Polynomial-time Algorithms for Energy Games with Special Weight Structures
    Chatterjee, Krishnendu and Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon In: 20th Annual European Symposium on Algorithms (ESA 2012) , 10-12 Sep 2012 , Ljubljana, Slovenia (2012)

  • Maintaining Large Dense Subgraphs on Dynamic Networks
    Das Sarma, Atish and Lall, Ashwin and Nanongkai, Danupon and Trehan, Amitabh In: 26th International Symposium on DIStributed Computing , 16-18 Oct 2012 , Salvador-Bahia, Brazil (In Press) (2012)

  • Distributed verification and hardness of distributed approximation
    Das Sarma, Atish and Holzer, Stephan and Kor, Liah and Korman, Amos and Nanongkai, Danupon and Pandurangan, Gopal and Peleg, David and Wattenhofer, Roger In: STOC '11 Proceedings of the 43rd annual ACM symposium on Theory of computing , 2011, June 4-11 , San Jose, CA, USA (2011)

  • A tight unconditional lower bound on distributed randomwalk computation
    Nanongkai, Danupon and Das Sarma, Atish and Pandurangan, Gopal In: PODC '11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing , 2011, June 4-11 , San Jose, CA, USA (2011)

  • Representative Skylines using Threshold-based Preference Distributions
    Das Sarma, Atish and Lall, Ashwin and Nanongkai, Danupon and Lipton, Richard J. and Jim, Xu In: International Conference on Data Engineering , 11-16 April, 2011 , Hannover, Germany (In Press) (2011)

    • Book Section/Chapter

  • Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
    Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon In: Encyclopedia of Algorithms. Springer, pp. 600-602 (2016)

    • This list was generated on Sat Nov 9 07:50:01 2024 CET.
    Universität Wien| Fakultät für Informatik | Währinger Straße 29 | 1090 Wien | T +43-1-4277-780 01 | Imprint | Webteam
    EPrints Logo
    CS is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.