Суммарная раскраска
В теории графов суммарная раскраска графа — это маркировка его вершин положительными целыми числами, при которой никакие две соседние вершины не имеют одинаковых меток, что минимизирует сумму меток. Минимальная сумма, которую можно достичь, называется хроматической суммой графа. [1] Хроматические суммы и раскраска сумм были введены Суповитом в 1987 году с использованием терминологии, не связанной с теорией графов. [2] и впервые изучена с точки зрения теории графов Евой Кубицкой (независимо от Суповита) в ее докторской диссертации 1989 года. [3]
Для получения хроматической суммы может потребоваться использование более различных меток, чем хроматическое число графа, идаже если хроматическое число графа ограничено, количество различных меток, необходимых для получения оптимальной хроматической суммы, может быть сколь угодно большим. [4]
Вычисление хроматической суммы NP-сложно . Однако его можно вычислить за линейное время для деревьев и псевдодеревьев . [5] [6] и за полиномиальное время для внешнепланарных графов . [6] Существует алгоритм аппроксимации с постоянным коэффициентом для интервальных и двудольных графов . [7] [8] Случай интервального графа остается NP-сложным. [9] Это случай, возникающий в оригинальном приложении Supovit при проектировании СБИС , а также в приложениях для планирования . [7]
Ссылки
[ редактировать ]- ^ Малафиейский, Михал (2004), «Суммальная раскраска графов», Кубале, Марек (ред.), Раскраски графов , Современная математика, том. 352, Провиденс, Род-Айленд: Американское математическое общество, стр. 55–65, doi : 10.1090/conm/352/06372 , ISBN. 9780821834589 , МР 2076989
- ^ Суповит, К.Дж. (1987), «Нахождение максимального планарного подмножества набора цепей в канале», Транзакции IEEE по компьютерному проектированию интегральных схем и систем , 6 (1): 93–94, doi : 10.1109/tcad .1987.1270250 , S2CID 14949711
- ^ Кубицка, Ева Мария (1989), Хроматическая сумма и эффективные алгоритмы дерева , доктор философии. диссертация, Университет Западного Мичигана, MR 2637573
- ^ Эрдеш, Пол ; Кубицка, Ева ; Швенк, Аллен Дж. (1990), «Графики, которым требуется много цветов для достижения их хроматической суммы», Труды двадцатой Юго-восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1989), Congressus Numerantium , 71 : 17–28, МР 1041612
- ^ Кубицка, Ева ; Швенк, Аллен Дж. (1989), «Введение в хроматические суммы», Труды 17-й конференции ACM по компьютерным наукам (CSC '89) , Нью-Йорк, штат Нью-Йорк, США: ACM, стр. 39–45, doi : 10.1145/ 75427.75430 , ISBN 978-0-89791-299-0 , S2CID 28544302
- ^ Jump up to: а б Кубицка, Ева М. (2005), «Полиномиальный алгоритм нахождения хроматической суммы для унициклических и внешнепланарных графов», Ars Combinatoria , 76 : 193–201, MR 2152758
- ^ Jump up to: а б Халльдорссон, Магнус М.; Корцарз, Гай; Шахнай, Хадас (2001), «Минимизация среднего завершения отдельных задач и интервальных графиков», Аппроксимация, рандомизация и комбинаторная оптимизация (Беркли, Калифорния, 2001) , Конспекты лекций по информатике, том. 2129, Берлин: Springer, стр. 114–126, номер документа : 10.1007/3-540-44666-4_15 , ISBN. 978-3-540-42470-3 , МР 1910356
- ^ Джаро, Кшиштоф; Янчевски, Роберт; Кубале, Марек; Малафейский, Михал (2002), «Алгоритм аппроксимации 27/26 для раскраски хроматической суммы двудольных графов», Алгоритмы аппроксимации для комбинаторной оптимизации , Конспекты лекций по информатике, том. 2462, Берлин: Springer, стр. 135–145, номер документа : 10.1007/3-540-45753-4_13 , ISBN. 978-3-540-44186-1 , МР 2091822
- ^ Маркс, Даниэль (2005), «Краткое доказательство NP-полноты раскраски интервалов минимальной суммы», Operations Research Letters , 33 (4): 382–384, CiteSeerX 10.1.1.5.2707 , doi : 10.1016/j.orl .2004.07.006 , МР 2127409