Приближенный алгоритм для хроматической раскраски двудольных графов за полиномиальное в среднем время
https://doi.org/10.15514/ISPRAS-2015-27(5)-11
Аннотация
Известно что если P≠NP то задача аппроксимации суммарной раскраски двудольных графов не может быть осуществлена в полиномиальное время с точностью для некоторой константы . Мы предлагаем для сколь угодно малого приближенный алгоритм для данной проблемы который работает за полиномиальное в среднем время.
Об авторах
А. С. Асратян
Linkopings Universitet, Department of Mathematics
Швеция
Швеция
Н. Н. Кузюрин
ИСП РАН
Россия
Россия
Список литературы
1. B. Bollobas, Random graphs, second ed., Cambridge Univ. Press, Cambridge, 2001.
2. B. Bollobas, The chromatic number of random graphs, Combinatorica, 1988, v. 8, c. 49-55.
3. A. Frieze,C. McDiarmid, Algorithmic theory of random graphs, Random Structures and Algorithms, Jan.-March 1997, v. 10, n. 1-2, c. 5-42.
4. L. Kucera, The greedy coloring is a bad probabilistic algorithm, J. of Algorithms, Dec. 1991, v. 12, n. 4, c. 674-684.
5. R. Motwani and P. Raghavan, Randomized algorithms, Cambridge Univ. Press, 1995.
6. E. Kubicka, A.J. Schwenk, An introduction to chromatic sums, Proc. of ACM Computer Science Conference, 1989, c. 39-45.
7. A. Bar-Noy, G. Kortsarz, Minimum color sum of bipartite graphs, J. of Algorithms, 1998, v. 28, c. 339-365.
8. K. Giaro, R. Janczewski, M. Kubale, M. Malafiejski, A 27/26-approximation algorithm for the chromatic sum coloring of bipartite graphs, Proc. APPROX 2002, LNCS v. 2462, c. 135-145.
9. M. Krivelevich , V.H. Vu, Approximating the independence number and the chromatic number in expected polynomial time, J. Combin. Optimization, 2002, v. 6, c. 143-155.
Рецензия
Для цитирования:
Асратян А.С., Кузюрин Н.Н. Приближенный алгоритм для хроматической раскраски двудольных графов за полиномиальное в среднем время. Труды Института системного программирования РАН. 2015;27(5):191-198. https://doi.org/10.15514/ISPRAS-2015-27(5)-11
For citation:
Asratian A.S., Kuzyurin N.N. Approximating chromatic sum coloring of bipartite graphs in expected polynomial time. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2015;27(5):191-198. (In Russ.) https://doi.org/10.15514/ISPRAS-2015-27(5)-11
Послать статью по эл. почте 