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

Nanongkai, Danupon

  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. A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
    2019/10/17 by Chuzhoy, Julia, Gao, Yu, Li, Jason +3 · 12 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  3. Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update\n Time
    2017/08/13 by Danupon Nanongkai, Thatchaphol Saranurak, Nanongkai, Danupon +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
  4. 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
  5. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on\n One-Pass Dynamic Streams
    2015/04/09 by Sayan Bhattacharya, Bhattacharya, Sayan, Monika Henzinger +5 · 5 citations
    Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Advanced Graph Theory Research
  6. 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
  7. Dynamic Algorithms for Graph Coloring
    2017/11/12 by Bhattacharya, Sayan, Chakrabarty, Deeparnab, Henzinger, Monika +1 · 5 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  8. A New Deterministic Algorithm for Dynamic Set Cover
    2019/09/25 by Sayan Bhattacharya, Bhattacharya, Sayan, Monika Henzinger +3 · 5 citations
    Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Computational Geometry and Mesh Generation
  9. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
    2020/04/17 by Bernstein, Aaron, Brand, Jan van den, Gutenberg, Maximilian Probst +4 · 5 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  10. Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
    2020/02/25 by Sayan Bhattacharya, Bhattacharya, Sayan, Monika Henzinger +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
  11. Vertex Connectivity in Poly-logarithmic Max-flows
    2021/03/31 by Li, Jason, Nanongkai, Danupon, Panigrahi, Debmalya +2 · 4 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  12. Near-Linear Time Approximations for Cut Problems via Fair Cuts
    2022/03/01 by Li, Jason, Nanongkai, Danupon, Panigrahi, Debmalya +1 · 4 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  13. 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
  14. Can Quantum Communication Speed Up Distributed Computation?
    2012/07/22 by Michael Elkin, Hartmut Klauck, Elkin, Michael +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)
  15. Nearly Optimal Communication and Query Complexity of Bipartite Matching
    2022/08/04 by Blikstad, Joakim, Brand, Jan van den, Efron, Yuval +2 · 4 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  16. 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
  17. A Note on Isolating Cut Lemma for Submodular Function Minimization
    2021/03/29 by Mukhopadhyay, Sagnik, Nanongkai, Danupon · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  18. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
    2017/08/14 by Chalermsook, Parinya, Cygan, Marek, Kortsarz, Guy +4 · 2 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  19. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds
    2019/05/13 by Jan van den Brand, Danupon Nanongkai, Brand, Jan van den +3 · 2 citations
    Computer Science · #Graph Theory and Algorithms #Matrix Theory and Algorithms #Stochastic Gradient Optimization Techniques
  20. Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
    2019/10/31 by Forster, Sebastian, Nanongkai, Danupon, Saranurak, Thatchaphol +2 · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  21. 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
  22. Minimum Cuts in Directed Graphs via Partial Sparsification
    2021/11/17 by Ruoxu Cen, Jason Li, Cen, Ruoxu +9 · 4 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
  23. Faster Algorithms for Semi-Matching Problems
    2010/04/20 by Fakcharoenphol, Jittat, Laekhanukit, Bundit, Nanongkai, Danupon · 1 citation
    #05C85 #68P05 #90B35 #Data Structures and Algorithms (cs.DS) #E.1 #F.2.2 #FOS: Computer and information sciences #G.2.2
  24. 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)
  25. 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)
  26. 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)
  27. Distributed Random Walks
    2013/02/19 by Sarma, Atish Das, Nanongkai, Danupon, Pandurangan, Gopal +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Distributed #F.2.2 #FOS: Computer and information sciences #G.2.2 #Parallel #and Cluster Computing (cs.DC)
  28. Almost-Tight Distributed Minimum Cut Algorithms
    2014/08/04 by Danupon Nanongkai, Nanongkai, Danupon, Hsin-Hao Su +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)
  29. Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n1/2-ε)-Time
    2016/11/11 by Nanongkai, Danupon, Saranurak, Thatchaphol · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  30. 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
  31. Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
    2018/11/08 by Bernstein, Aaron, Nanongkai, Danupon · 1 citation
    #C.2.4 #Data Structures and Algorithms (cs.DS) #Distributed #F.2.0 #FOS: Computer and information sciences #G.2.2 #Parallel #and Cluster Computing (cs.DC)
  32. Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time
    2019/09/24 by Jan van den Brand, Brand, Jan van den, Danupon Nanongkai +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
  33. Equivalence Classes and Conditional Hardness in Massively Parallel Computations
    2020/01/07 by Nanongkai, Danupon, Scquizzato, Michele · 1 citation
    #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
  34. Distributed Weighted Min-Cut in Nearly-Optimal Time
    2020/04/20 by Dory, Michal, Efron, Yuval, Mukhopadhyay, Sagnik +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
  35. Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
    2022/05/30 by Chalermsook, Parinya, Huang, Chien-Chung, Nanongkai, Danupon +3 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  36. Fast Algorithms via Dynamic-Oracle Matroids
    2023/02/20 by Blikstad, Joakim, Mukhopadhyay, Sagnik, Nanongkai, Danupon +1 · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  37. Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
    2023/03/01 by Ashvinkumar, Vikrant, Bernstein, Aaron, Cao, Nairen +5 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
  38. Shortcuts and Transitive-Closure Spanners Approximation
    2025/02/12 by Parinya Chalermsook, Chalermsook, Parinya, Yonggang Jiang +5 · 1 citation
    Engineering · #Advanced Numerical Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences