4 papers
The Complexity Landscape of Distributed Locally Checkable Problems on Trees
Yi-Jun Chang
Recent research revealed the existence of gaps in the complexity landscape of locally checkable labeling (LCL) problems in the LOCAL model of distributed computing. For example, th…
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,…
Narrowing the LOCAL$\unicode{x2013}$CONGEST Gaps in Sparse Networks via Expander Decompositions
Yi-Jun Chang, Hsin-Hao Su
Many combinatorial optimization problems can be approximated within factors in rounds in the LOCAL model via network decompositions [Ghaffa…
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…