کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952251 | 1442024 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Acyclic edge coloring through the Lovász Local Lemma
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Acyclic edge coloring through the Lovász Local Lemma Acyclic edge coloring through the Lovász Local Lemma](/preview/png/4952251.png)
چکیده انگلیسی
We give a probabilistic analysis of a Moser-type algorithm for the Lovász Local Lemma (LLL), adjusted to search for acyclic edge colorings of a graph. We thus improve the best known upper bound to acyclic chromatic index, also obtained by analyzing a similar algorithm, but through the entropic method (basically counting argument). Specifically we show that a graph with maximum degree Î has an acyclic proper edge coloring with at most â3.74(Îâ1)â+1 colors, whereas, previously, the best bound was 4(Îâ1). The main contribution of this work is that it comprises a probabilistic analysis of a Moser-type algorithm applied to events pertaining to dependent variables.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 665, 22 February 2017, Pages 40-50
Journal: Theoretical Computer Science - Volume 665, 22 February 2017, Pages 40-50
نویسندگان
Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos,