Danupon Nanongkai

research

∙ 03/01/2023

Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights

This paper presents parallel and distributed algorithms for single-sourc...

0 Vikrant Ashvinkumar, et al. ∙

research

∙ 02/20/2023

Fast Algorithms via Dynamic-Oracle Matroids

We initiate the study of matroid problems in a new oracle model called d...

0 Joakim Blikstad, et al. ∙

research

∙ 02/12/2023

Fully Dynamic Exact Edge Connectivity in Sublinear Time

Given a simple n-vertex, m-edge graph G undergoing edge insertions and d...

0 Gramoz Goranci, et al. ∙

research

∙ 08/04/2022

Nearly Optimal Communication and Query Complexity of Bipartite Matching

We settle the complexities of the maximum-cardinality bipartite matching...

0 Joakim Blikstad, et al. ∙

research

∙ 05/30/2022

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

In the k-edge-connected spanning subgraph (kECSS) problem, our goal is t...

0 Parinya Chalermsook, et al. ∙

research

∙ 03/07/2022

Negative-Weight Single-Source Shortest Paths in Near-linear Time

We present a randomized algorithm that computes single-source shortest p...

0 Aaron Bernstein, et al. ∙

research

∙ 03/01/2022

Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time

In this paper, we introduce a robust notion of (1+ϵ)-approximate (s, t)-...

0 Jason Li, et al. ∙

research

∙ 01/14/2022

Cut query algorithms with star contraction

We study the complexity of determining the edge connectivity of a simple...

0 Simon Apers, et al. ∙

research

∙ 11/17/2021

Minimum Cuts in Directed Graphs via Partial Sparsification

We give an algorithm to find a minimum cut in an edge-weighted directed ...

0 Ruoxu Cen, et al. ∙

research

∙ 04/16/2021

Minimum Cuts in Directed Graphs via √(n) Max-Flows

We give an algorithm to find a mincut in an n-vertex, m-edge weighted di...

0 Ruoxu Cen, et al. ∙

research

∙ 03/31/2021

Vertex Connectivity in Poly-logarithmic Max-flows

The vertex connectivity of an m-edge n-vertex undirected graph is the sm...

0 Jason Li, et al. ∙

research

∙ 03/29/2021

A Note on Isolating Cut Lemma for Submodular Function Minimization

It has been observed independently by many researchers that the isolatin...

0 Sagnik Mukhopadhyay, et al. ∙

research

∙ 02/12/2021

Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs

We present the first work-optimal polylogarithmic-depth parallel algorit...

0 Andrés López-Martínez, et al. ∙

research

∙ 02/10/2021

Breaking the Quadratic Barrier for Matroid Intersection

The matroid intersection problem is a fundamental problem that has been ...

0 Joakim Blikstad, et al. ∙

research

∙ 11/16/2020

Faster connectivity in low-rank hypergraphs via expander decomposition

We design an algorithm for computing connectivity in hypergraphs which r...

0 Calvin Beideman, et al. ∙

research

∙ 09/03/2020

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

We present an Õ(m+n^1.5)-time randomized algorithm for maximum cardinali...

0 Jan van den Brand, et al. ∙

research

∙ 04/20/2020

Distributed Weighted Min-Cut in Nearly-Optimal Time

Minimum-weight cut (min-cut) is a basic measure of a network's connectiv...

0 Michal Dory, et al. ∙

research

∙ 04/17/2020

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary

Designing dynamic graph algorithms against an adaptive adversary is a ma...

0 Aaron Bernstein, et al. ∙

research

∙ 02/25/2020

Dynamic Set Cover: Improved Amortized and Worst-Case Update Time

In the dynamic minimum set cover problem, a challenge is to minimize the...

0 Sayan Bhattacharya, et al. ∙

research

∙ 02/25/2020

An Improved Algorithm for Dynamic Set Cover

We consider the minimum set cover problem in a dynamic setting. Here, we...

0 Sayan Bhattacharya, et al. ∙

research

∙ 01/07/2020

Equivalence Classes and Conditional Hardness in Massively Parallel Computations

The Massively Parallel Computation (MPC) model serves as a common abstra...

0 Danupon Nanongkai, et al. ∙

research

∙ 01/02/2020

Coarse-Grained Complexity for Dynamic Algorithms

To date, the only way to argue polynomial lower bounds for dynamic algor...

0 Sayan Bhattacharya, et al. ∙

research

∙ 11/05/2019

Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms

Consider the following 2-respecting min-cut problem. Given a weighted g...

0 Sagnik Mukhopadhyay, et al. ∙

research

∙ 10/31/2019

Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms

Consider the following "local" cut-detection problem in a directed graph...

0 Sebastian Forster, et al. ∙

research

∙ 10/17/2019

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond

We consider the classical Minimum Balanced Cut problem: given a graph G,...

0 Julia Chuzhoy, et al. ∙

research

∙ 10/17/2019

Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex

We study deterministic algorithms for computing graph cuts, with focus o...

0 Yu Gao, et al. ∙

research

∙ 09/25/2019

A New Deterministic Algorithm for Dynamic Set Cover

We present a deterministic dynamic algorithm for maintaining a (1+ϵ)f-ap...

0 Sayan Bhattacharya, et al. ∙

research

∙ 09/24/2019

Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time

Consider the following distance query for an n-node graph G undergoing e...

0 Jan van den Brand, et al. ∙

research

∙ 05/14/2019

Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries

We present a new, simple, algorithm for the local vertex connectivity pr...

0 Danupon Nanongkai, et al. ∙

research

∙ 05/13/2019

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds

The dynamic matrix inverse problem is to maintain the inverse of a matri...

0 Jan van den Brand, et al. ∙

research

∙ 04/09/2019

Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme

Vertex connectivity a classic extensively-studied problem. Given an inte...

0 Danupon Nanongkai, et al. ∙

research

∙ 04/08/2019

Distributed Edge Connectivity in Sublinear Time

We present the first sublinear-time algorithm for a distributed message-...

0 Mohit Daga, et al. ∙

research

∙ 11/08/2018

Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time

In the distributed all-pairs shortest paths problem (APSP), every node ...

0 Aaron Bernstein, et al. ∙

research

∙ 11/12/2017

Dynamic Algorithms for Graph Coloring

We design fast dynamic algorithms for proper vertex and edge colorings i...

0 Sayan Bhattacharya, et al. ∙

research

∙ 11/03/2017

A Faster Distributed Single-Source Shortest Paths Algorithm

We devise new algorithms for the single-source shortest paths problem in...

0 Sebastian Krinninger, et al. ∙

research

∙ 08/14/2017

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

We consider questions that arise from the intersection between the areas...

0 Parinya Chalermsook, et al. ∙

research

∙ 08/11/2017

New Tools and Connections for Exponential-time Approximation

In this paper, we develop new tools and connections for exponential time...

0 Nikhil Bansal, et al. ∙

Danupon Nanongkai

Featured Co-authors