Jump to content

Суммарная раскраска

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

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

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

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

  1. ^ Малафиейский, Михал (2004), «Суммальная раскраска графов», Кубале, Марек (ред.), Раскраски графов , Современная математика, том. 352, Провиденс, Род-Айленд: Американское математическое общество, стр. 55–65, doi : 10.1090/conm/352/06372 , ISBN.  9780821834589 , МР   2076989
  2. ^ Суповит, К.Дж. (1987), «Нахождение максимального планарного подмножества набора цепей в канале», Транзакции IEEE по компьютерному проектированию интегральных схем и систем , 6 (1): 93–94, doi : 10.1109/tcad .1987.1270250 , S2CID   14949711
  3. ^ Кубицка, Ева Мария (1989), Хроматическая сумма и эффективные алгоритмы дерева , доктор философии. диссертация, Университет Западного Мичигана, MR   2637573
  4. ^ Эрдеш, Пол ; Кубицка, Ева ; Швенк, Аллен Дж. (1990), «Графики, которым требуется много цветов для достижения их хроматической суммы», Труды двадцатой Юго-восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1989), Congressus Numerantium , 71 : 17–28, МР   1041612
  5. ^ Кубицка, Ева ; Швенк, Аллен Дж. (1989), «Введение в хроматические суммы», Труды 17-й конференции ACM по компьютерным наукам (CSC '89) , Нью-Йорк, штат Нью-Йорк, США: ACM, стр. 39–45, doi : 10.1145/ 75427.75430 , ISBN  978-0-89791-299-0 , S2CID   28544302
  6. ^ Jump up to: а б Кубицка, Ева М. (2005), «Полиномиальный алгоритм нахождения хроматической суммы для унициклических и внешнепланарных графов», Ars Combinatoria , 76 : 193–201, MR   2152758
  7. ^ Jump up to: а б Халльдорссон, Магнус М.; Корцарз, Гай; Шахнай, Хадас (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-полноты раскраски интервалов минимальной суммы», Operations Research Letters , 33 (4): 382–384, CiteSeerX   10.1.1.5.2707 , doi : 10.1016/j.orl .2004.07.006 , МР   2127409
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 0ecd664a14a121d02aa2089798c8abe0__1721275740
URL1:https://arc.ask3.ru/arc/aa/0e/e0/0ecd664a14a121d02aa2089798c8abe0.html
Заголовок, (Title) документа по адресу, URL1:
Sum coloring - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)