15 citations · 41 across the 17 of their papers we have counts for
20 papers
A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
Ran Duan, Jiayi Mao, Xinkai Shu +1
In undirected graphs with real non-negative weights, we give a new randomized algorithm for the single-source shortest path (SSSP) problem with running time $O(m\sqrt{\log n \cdot…
Faster Matrix Multiplication via Asymmetric Hashing
Ran Duan, Hongxun Wu, Renfei Zhou
Fast matrix multiplication is one of the most fundamental problems in algorithm research. The exponent of the optimal time complexity of matrix multiplication is usually denoted by…
Faster Min-Plus Product for Monotone Instances
Shucheng Chi, Ran Duan, Tianle Xie +1
In this paper, we show that the time complexity of monotone min-plus product of two matrices is , where is the f…
Maintaining Exact Distances under Multiple Edge Failures
Ran Duan, Hanlin Ren
We present the first compact distance oracle that tolerates multiple failures and maintains exact distances. Given an undirected weighted graph and an arbitrarily larg…
Faster Algorithms for Bounded-Difference Min-Plus Product
Shucheng Chi, Ran Duan, Tianle Xie
Min-plus product of two matrices is a fundamental problem in algorithm research. It is known to be equivalent to APSP, and in general it has no truly subcubic algorithm…
Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election
Yi-Jun Chang, Ran Duan, Shunhua Jiang
We consider the energy complexity of the leader election problem in the single-hop radio network model, where each device has a unique identifier in . Energy i…
A Scaling Algorithm for Weighted -Factors in General Graphs
Ran Duan, Haoqing He, Tianyi Zhang
We study the maximum weight perfect -factor problem on any general simple graph with positive integral edge weights , and , . When we have a functio…
Approximate Distance Oracles Subject to Multiple Vertex Failures
Ran Duan, Yong Gu, Hanlin Ren
Given an undirected graph of vertices and edges with weights in , we construct vertex sensitive distance oracles (VSDO), which are data structures that pre…
Faster Algorithms for All Pairs Non-decreasing Paths Problem
Ran Duan, Ce Jin, Hongxun Wu
In this paper, we present an improved algorithm for the All Pairs Non-decreasing Paths (APNP) problem on weighted simple digraphs, which has running time $\tilde{O}(n^{\frac{3 + ω}…
Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs
Ran Duan, Kaifeng Lyu, Hongxun Wu +1
In a directed graph with a capacity on every edge, a \emph{bottleneck path} (or \emph{widest path}) between two vertices is a path maximizing the minimum capacity of edge…
Near-linear Time Algorithm for Approximate Minimum Degree Spanning Trees
Ran Duan, Haoqing He, Tianyi Zhang
Given a graph , we wish to compute a spanning tree whose maximum vertex degree, i.e. tree degree, is as small as possible. Computing the exact optimal solution is known…
Purely Combinatorial Algorithms for Approximate Directed Minimum Degree Spanning Trees
Ran Duan, Tianyi Zhang
Given a directed graph on vertices with a special vertex , the directed minimum degree spanning tree problem requires computing a incoming spanning tree rooted at wh…
Faster Randomized Worst-Case Update Time for Dynamic Subgraph Connectivity
Ran Duan, Le Zhang
Real-world networks are prone to breakdowns. Typically in the underlying graph , besides the insertion or deletion of edges, the set of active vertices changes overtime. A verte…
Connectivity Oracles for Graphs Subject to Vertex Failures
Ran Duan, Seth Pettie
We introduce new data structures for answering connectivity queries in graphs subject to batched vertex failures. A deterministic structure processes a batch of f…
An Improved Algorithm for Incremental DFS Tree in Undirected Graphs
Lijie Chen, Ran Duan, Ruosong Wang +2
Depth first search (DFS) tree is one of the most well-known data structures for designing efficient graph algorithms. Given an undirected graph with vertices and …
Improved distance sensitivity oracles via tree partitioning
Ran Duan, Tianyi Zhang
We introduce an improved structure of distance sensitivity oracle (DSO). The task is to pre-process a non-negatively weighted graph so that a data structure can quickly answer repl…
An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
Rann Duan, Jugal Garg, Kurt Mehlhorn
We present an improved combinatorial algorithm for the computation of equilibrium prices in the linear Arrow-Debreu model. For a market with agents and integral utilities bound…
Scaling Algorithms for Weighted Matching in General Graphs
Ran Duan, Seth Pettie, Hsin-Hao Su
We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in time, $O(m\sqrt{n…
A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
Ran Duan, Kurt Mehlhorn
We present the first combinatorial polynomial time algorithm for computing the equilibrium of the Arrow-Debreu market model with linear utilities.
Scaling algorithms for approximate and exact maximum weight matching
Ran Duan, Seth Pettie, Hsin-Hao Su
The {\em maximum cardinality} and {\em maximum weight matching} problems can be solved in time , a bound that has resisted improvement despite decades of rese…