6 citations · 14 across the 8 of their papers we have counts for
10 papers
Hardness and Approximation Algorithms for Balanced Districting Problems
Prathamesh Dharangutte, Jie Gao, Shang-En Huang +1
We introduce and study the problem of balanced districting, where given an undirected graph with vertices carrying two types of weights (different population, resource types, etc)…
Deterministic Expander Routing: Faster and More Versatile
Yi-Jun Chang, Shang-En Huang, Hsin-Hao Su
We consider the expander routing problem formulated by Ghaffari, Kuhn, and Su (PODC 2017), where the goal is to route all the tokens to their destinations given that each vertex is…
Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds
Nairen Cao, Shang-En Huang, Hsin-Hao Su
In this paper, we study parallel algorithms for the correlation clustering problem, where every pair of two different entities is labeled with similar or dissimilar. The goal is to…
-Approximate Maximum Weighted Matching in Distributed, Parallel, and Semi-Streaming Settings
Shang-En Huang, Hsin-Hao Su
The maximum weighted matching (MWM) problem is one of the most well-studied combinatorial optimization problems in distributed graph algorithms. Despite a long development on the p…
Vertex Sparsifiers for Hyperedge Connectivity
Han Jiang, Shang-En Huang, Thatchaphol Saranurak +1
Recently, Chalermsook et al. [SODA'21(arXiv:2007.07862)] introduces a notion of vertex sparsifiers for -edge connectivity, which has found applications in parameterized algorith…
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection
Shang-En Huang, Seth Pettie, Leqi Zhu
Since the mid-1980s it has been known that Byzantine Agreement can be solved with probability 1 asynchronously, even against an omniscient, computationally unbounded adversary that…
Byzantine Agreement in Polynomial Time with Near-Optimal Resilience
Shang-En Huang, Seth Pettie, Leqi Zhu
It has been known since the early 1980s that Byzantine Agreement in the full information, asynchronous model is impossible to solve deterministically against even one crash fault […
Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts
Shang-En Huang, Seth Pettie
We prove better lower bounds on additive spanners and emulators, which are lossy compression schemes for undirected graphs, as well as lower bounds on shortcut sets, which reduce t…
Thorup-Zwick Emulators are Universally Optimal Hopsets
Shang-En Huang, Seth Pettie
A - is, informally, a weighted edge set that, when added to a graph, allows one to get from point to point using a path with at most edges ("hop…
Fully Dynamic Connectivity in Amortized Expected Time
Shang-En Huang, Dawei Huang, Tsvi Kopelowitz +2
Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a randomized Las Vegas dynamic connectivity data structure with $O(\log n(\log\…