10 citations · 26 across the 13 of their papers we have counts for
5 papers · 1 filter
The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
Yi-Jun Chang, Zeyong Li
In this paper, we present a low-diameter decomposition algorithm in the LOCAL model of distributed computing that succeeds with probability . Specifically, we show h…
Ortho-Radial Drawing in Near-Linear Time
Yi-Jun Chang
An orthogonal drawing is an embedding of a plane graph into a grid. In a seminal work of Tamassia (SIAM Journal on Computing 1987), a simple combinatorial characterization of angle…
Universally Optimal Deterministic Broadcasting in the HYBRID Distributed Model
Yi-Jun Chang, Oren Hecht, Dean Leitersdorf
In theoretical computer science, it is a common practice to show existential lower bounds for problems, meaning there is a family of pathological inputs on which no algorithm can d…
Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs
Yi-Jun Chang, Da Wei Zheng
We consider the massively parallel computation (MPC) model, which is a theoretical abstraction of large-scale parallel processing models such as MapReduce. In this model, assuming…
Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
Yi-Jun Chang
In the LOCAL model, low-diameter decomposition is a useful tool in designing algorithms, as it allows us to shift from the general graph setting to the low-diameter graph setting,…