Суммарная раскраска - Википедия - Sum coloring

Суммарная окраска дерева. Сумма меток равна 11, что меньше, чем можно было бы получить, используя только две метки.

В теория графов, а раскраска суммы графа - это разметка его вершин положительными целыми числами без двух соседних вершин с одинаковыми метками, что минимизирует сумму меток. Минимальная сумма, которая может быть достигнута, называется хроматическая сумма графа.[1] Хроматические суммы и раскраска сумм были введены Суповитом в 1987 году с использованием терминологии, не связанной с теорией графов,[2] и впервые изучены в терминах теории графов Ева Кубичка (независимо от Суповит) в ее докторской диссертации 1989 г.[3]

Для получения хроматической суммы может потребоваться использование более различных меток, чем хроматическое число графика, и даже когда хроматическое число графа ограничено, количество различных меток, необходимых для получения оптимальной хроматической суммы, может быть сколь угодно большим.[4]

Вычисление хроматической суммы NP-жесткий. Однако это может быть вычислено в линейное время за деревья и псевдодеревья,[5][6] И в полиномиальное время за внешнепланарные графы.[6] Есть постоянный коэффициент алгоритм аппроксимации за интервальные графики и для двудольные графы.[7][8] Случай интервального графа остается NP-трудным.[9] Это дело, возникающее в первоначальном заявлении Суповита в СБИС дизайн, а также имеет приложения в планирование.[7]

Рекомендации

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