.png){kind=icon}
返回
Tree coloring with predictions
.png){kind=icon}
OA
AI
DOI：10.1016/j.dam.2025.10.024.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Graph coloring is a notoriously challenging problem, especially when considering the online setting where each arriving vertex must be colored immediately and irreversibly. Even on trees, which are trivially two-colorable, achieving anything better than a logarithmic competitive ratio becomes impossible if the order of arrival is adversarially determined. We investigate tree coloring in a slightly relaxed model where vertices arrive online but in random order, focusing specifically on algorithms with predictions of varying reliability. Furthermore, we extend our analysis to all two-colorable graphs and provide matching lower bounds for both cases. (c) 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keyword:
Online graph coloring
Competitive ratio
Random order
Predictions
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
D
IF:
1.1
论文数:
352
被引数:
7.7K
机构
查看更多机构
引用论文
.png){kind=icon}
分享收藏 没有更多内容