Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2026
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,…
cs.DS2025
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…