Efficiently list-edge coloring multigraphs asymptotically optimally
Efficiently list-edge coloring multigraphs asymptotically optimally
复制标题
有效地渐进最优地列出边缘着色多重图
DOI：
10.1137/1.9781611975994.142
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sinclair, Alistair
中科院分区：
文献类型：
--
作者：
Iliopoulos, Fotis;Sinclair, Alistair
我们给出Kahn的开创性结果的多项式时间算法，Kahn证明了（列表-）边着色重图的Goldberg-Seymour和列表着色图渐近成立。卡恩的论点是基于概率的方法，是非建设性的。我们的关键见解是，我们可以将Achlioptas，Iliopoulos和Kolmogorov用于分析局部搜索算法的复杂技术与Kahn使用的匹配概率空间的相关衰减特性相结合，以构建有效的边着色算法。
We give polynomial time algorithms for the seminal results of Kahn, who showed that the Goldberg–Seymour and list‐coloring conjectures for (list‐)edge coloring multigraphs hold asymptotically. Kahn's arguments are based on the probabilistic method and are non‐constructive. Our key insight is that we can combine sophisticated techniques due to Achlioptas, Iliopoulos, and Kolmogorov for the analysis of local search algorithms with correlation decay properties of the probability spaces on matchings used by Kahn in order to construct efficient edge‐coloring algorithms.