Simple and Asymptotically Optimal Online Bipartite Edge Coloring
arXiv (Cornell University)(2023)
摘要
We provide a simple online $\Delta(1+o(1))$-edge-coloring algorithm for
bipartite graphs of maximum degree $\Delta=\omega(\log n)$ under adversarial
vertex arrivals on one side of the graph. Our algorithm slightly improves the
result of (Cohen, Peng and Wajc, FOCS19), which was the first, and currently
only, to obtain an asymptotically optimal $\Delta(1+o(1))$ guarantee for an
adversarial arrival model. More importantly, our algorithm provides a new,
simpler approach for tackling online edge coloring.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要