86 citations · 243 across the 39 of their papers we have counts for
6 papers · 1 filter
An Optimal Distributed -Coloring Algorithm?
Yi-Jun Chang, Wenzheng Li, Seth Pettie
Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for -list coloring in the randomi…
The Energy Complexity of Broadcast
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes +3
Energy is often the most constrained resource in networks of battery-powered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (…
Distributed Edge Coloring with Small Palettes and a Special Case of the Constructive Lovász Local Lemma
Yi-Jun Chang, Qizheng He, Wenzheng Li +2
We explore the complexity of edge coloring in the LOCAL model in different palette size regimes. 1. Lower Bounds: First, we simplify the round elimination technique of Brandt et al…
Approximate Generalized Matching: -Factors and -Edge Covers
Dawei Huang, Seth Pettie
In this paper we present linear time approximation schemes for several generalized matching problems on nonbipartite graphs. Our results include -time algorithms for $(1-ε)…
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…
A Time Hierarchy Theorem for the LOCAL Model
Yi-Jun Chang, Seth Pettie
The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem ho…