vix.ing · top · new · best · stats · spec

Danupon Nanongkai

  1. Negative-Weight Single-Source Shortest Paths in Near-linear Time
    2022/03/07 by Aaron Bernstein, Bernstein, Aaron, Danupon Nanongkai +4 · 2 voices · 17 citations
    Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Algorithms and Data Compression
  2. Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update\n Time
    2017/08/13 by Danupon Nanongkai, Nanongkai, Danupon, Thatchaphol Saranurak +3 · 6 citations
    Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences
  3. Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
    2020/09/03 by Jan van den Brand, Yin-Tat Lee, Brand, Jan van den +13 · 8 citations
    Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques
  4. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on\n One-Pass Dynamic Streams
    2015/04/09 by Sayan Bhattacharya, Monika Henzinger, Bhattacharya, Sayan +5 · 5 citations
    Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Advanced Graph Theory Research
  5. Cut query algorithms with star contraction
    2022/01/14 by Simon Apers, Yuval Efron, Apers, Simon +9 · 7 citations
    Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Stochastic Gradient Optimization Techniques
  6. A New Deterministic Algorithm for Dynamic Set Cover
    2019/09/25 by Sayan Bhattacharya, Monika Henzinger, Bhattacharya, Sayan +3 · 5 citations
    Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Computational Geometry and Mesh Generation
  7. Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
    2020/02/25 by Sayan Bhattacharya, Monika Henzinger, Bhattacharya, Sayan +5 · 4 citations
    Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mathematical Approximation and Integration
  8. Breaking Quadratic Time for Small Vertex Connectivity and an\n Approximation Scheme
    2019/04/08 by Danupon Nanongkai, Nanongkai, Danupon, Thatchaphol Saranurak +3 · 3 citations
    Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems
  9. Can Quantum Communication Speed Up Distributed Computation?
    2012/07/22 by Michael Elkin, Elkin, Michael, Hartmut Klauck +5 · 2 citations
    Computer Science · #C.2.4 #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #F.0 #F.2.2 #FOS: Computer and information sciences #FOS: Physical sciences #G.2.2 #Parallel #Quantum Physics (quant-ph) #and Cluster Computing (cs.DC)
  10. Fully Dynamic Exact Edge Connectivity in Sublinear Time
    2023/02/12 by Gramoz Goranci, Goranci, Gramoz, Monika Henzinger +9 · 4 citations
    Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Interconnection Networks and Systems
  11. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds
    2019/05/13 by Jan van den Brand, Brand, Jan van den, Danupon Nanongkai +3 · 2 citations
    Computer Science · #Graph Theory and Algorithms #Matrix Theory and Algorithms #Stochastic Gradient Optimization Techniques
  12. Minimum Cuts in Directed Graphs via Partial Sparsification
    2021/11/17 by Ruoxu Cen, Jason Li, Cen, Ruoxu +9 · 5 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  13. New Deterministic Approximation Algorithms for Fully Dynamic Matching
    2016/04/19 by Sayan Bhattacharya, Monika Henzinger, Bhattacharya, Sayan +3 · 2 citations
    Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Privacy-Preserving Technologies in Data
  14. Distributed Verification and Hardness of Distributed Approximation
    2010/11/12 by Sarma, Atish Das, Holzer, Stephan, Kor, Liah +13 · 1 citation
    Computer Science · #Blockchain Technology Applications and Security #C.2.4 #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #F.0 #F.2.2 #FOS: Computer and information sciences #G.2.2 #Parallel #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
  15. A Tight Lower Bound on Distributed Random Walk Computation
    2011/02/14 by Danupon Nanongkai, Nanongkai, Danupon, Atish Das Sarma +3 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #F.2.2 #FOS: Computer and information sciences #G.2.2 #Parallel #and Cluster Computing (cs.DC)
  16. Dense Subgraphs on Dynamic Networks
    2012/08/07 by Atish Das Sarma, Sarma, Atish Das, Ashwin Lall +5 · 1 citation
    Computer Science · #C.2.4 #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #F.0 #F.2.2 #FOS: Computer and information sciences #G.2.2 #Parallel #Privacy-Preserving Technologies in Data #and Cluster Computing (cs.DC)
  17. Almost-Tight Distributed Minimum Cut Algorithms
    2014/08/04 by Danupon Nanongkai, Hsin-Hao Su, Nanongkai, Danupon +1 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
  18. Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n1/2-ε)-Time
    2016/11/11 by Danupon Nanongkai, Thatchaphol Saranurak, Nanongkai, Danupon +1 · 1 citation
    Computer Science · #Advanced Data Storage Technologies #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
  19. Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time
    2017/04/10 by Sayan Bhattacharya, Bhattacharya, Sayan, Monika Henzinger +3 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Privacy-Preserving Technologies in Data
  20. Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time
    2019/09/24 by Jan van den Brand, Danupon Nanongkai, Brand, Jan van den +1 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems
  21. Equivalence Classes and Conditional Hardness in Massively Parallel Computations
    2020/01/07 by Danupon Nanongkai, Michele Scquizzato, Nanongkai, Danupon +1 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Interconnection Networks and Systems #Parallel #and Cluster Computing (cs.DC)
  22. Shortcuts and Transitive-Closure Spanners Approximation
    2025/02/12 by Parinya Chalermsook, Yonggang Jiang, Chalermsook, Parinya +5 · 1 citation
    Engineering · #Advanced Numerical Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences