11 citations · 38 across the 12 of their papers we have counts for
12 papers
Parallel Point-to-Point Shortest Paths and Batch Queries
Xiaojun Dong, Andy Li, Yan Gu +1
We propose Orionet, efficient parallel implementations of Point-to-Point Shortest Paths (PPSP) queries using bidirectional search (BiDS) and other heuristics, with an additional fo…
Parallel -Core Decomposition: Theory and Practice
Youzhe Liu, Xiaojun Dong, Yan Gu +1
This paper proposes efficient solutions for -core decomposition with high parallelism. The problem of -core decomposition is fundamental in graph analysis and has application…
Parallel Contraction Hierarchies Can Be Efficient and Scalable
Zijin Wan, Xiaojun Dong, Letong Wang +3
Contraction Hierarchies (CH) (Geisberger et al., 2008) is one of the most widely used algorithms for shortest-path queries on road networks. Compared to Dijkstra's algorithm, CH en…
BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers
Brian Wheatman, Xiaojun Dong, Zheqi Shen +4
A fundamental building block in any graph algorithm is a graph container - a data structure used to represent the graph. Ideally, a graph container enables efficient access to the…
Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering
Laxman Dhulipala, Xiaojun Dong, Kishen N Gowda +1
Computing a Single-Linkage Dendrogram (SLD) is a key step in the classic single-linkage hierarchical clustering algorithm. Given an input edge-weighted tree , the SLD of is…
PASGAL: Parallel And Scalable Graph Algorithm Library
Xiaojun Dong, Yan Gu, Yihan Sun +1
In this paper, we introduce PASGAL (Parallel And Scalable Graph Algorithm Library), a parallel graph library that scales to a variety of graph types, many processors, and large gra…
Parallel Integer Sort: Theory and Practice
Xiaojun Dong, Laxman Dhulipala, Yan Gu +1
Integer sorting is a fundamental problem in computer science. This paper studies parallel integer sort both in theory and in practice. In theory, we show tighter bounds for a class…
Efficient Parallel Output-Sensitive Edit Distance
Xiangyun Ding, Xiaojun Dong, Yan Gu +2
Given two strings and , and a set of operations allowed to edit the strings, the edit distance between and is the minimum number of operations required t…
High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems
Xiaojun Dong, Yunshu Wu, Zhongqi Wang +3
Semisort is a fundamental algorithmic primitive widely used in the design and analysis of efficient parallel algorithms. It takes input as an array of records and a function extrac…
Parallel Strong Connectivity Based on Faster Reachability
Letong Wang, Xiaojun Dong, Yan Gu +1
Computing strongly connected components (SCC) is a fundamental problems in graph processing. As today's real-world graphs are getting larger and larger, parallel SCC is increasingl…
Provably Fast and Space-Efficient Parallel Biconnectivity
Xiaojun Dong, Letong Wang, Yan Gu +1
Biconnectivity is one of the most fundamental graph problems. The canonical parallel biconnectivity algorithm is the Tarjan-Vishkin algorithm, which has optimal work (numb…
Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
Xiaojun Dong, Yan Gu, Yihan Sun +1
In this paper, we study the single-source shortest-path (SSSP) problem with positive edge weights, which is a notoriously hard problem in the parallel context. In practice, the …