График допуска

В теории графов граф толерантности — это неориентированный граф , в котором каждая вершина может быть представлена замкнутым интервалом и действительным числом, называемым ее толерантностью, таким образом, что две вершины являются смежными в графе всякий раз, когда их интервалы перекрываются на длину, которая является, по крайней мере, минимумом из двух допусков. ^[1]Этот класс графов был представлен в 1982 году Мартином Чарльзом Голумбиком и Клайдом Монмой, которые использовали их для моделирования задач планирования , в которых моделируемые задачи могут совместно использовать ресурсы в течение ограниченного периода времени. ^[2]

Каждый график интервалов является графом допуска. ^[3] Граф дополнений каждого графа допусков представляет собой совершенно упорядочиваемый граф , из которого следует, что сами графы допусков являются совершенными графами . ^[4]

NP -полно определить, является ли данный граф графом допуска. ^[5]Однако, поскольку графы толерантности являются совершенными графами, многие алгоритмические проблемы, которые сложны для других классов графов, включая раскраску графа и проблему клики , могут быть решены за полиномиальное время на графах толерантности. ^[3]

Ссылки

^ Голумбик, Мартин Чарльз ; Тренк, Энн Н. (2004), Графики допусков , Кембриджские исследования по высшей математике, том. 89, Издательство Кембриджского университета, номер домена : 10.1017/CBO9780511542985 , ISBN. 0-521-82758-2 , МР 2051713
^ Голумбик, Мартин С .; Монма, Клайд Л. (1982), «Обобщение интервальных графов с допусками», Труды тринадцатой Юго-восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1982), Congressus Numerantium , 35 : 321–331 , МР 0725892
^ Jump up to: ^а ^б «Графкласс: толерантность» , Информационная система по классам графов и их включениям , получено 30 сентября 2019 г.
^ Голумбик, Мартин Чарльз ; Монма, Клайд Л.; Троттер, Уильям Т. младший (1984), «Графики допусков», Discrete Applied Mathematics , 9 (2): 157–170, doi : 10.1016/0166-218X(84)90016-7 , MR 0761599
^ Мерциос, Джордж Б.; Или Игнатий; Закс, Шмуэль (2011), «Распознавание толерантности и ограниченных графов толерантности» (PDF) , SIAM Journal on Computing , 40 (5): 1234–1257, doi : 10.1137/090780328 , MR 28545711

[gt-1] Голумбик, Мартин Чарльз ; Тренк, Энн Н. (2004), Графики допусков , Кембриджские исследования по высшей математике, том. 89, Издательство Кембриджского университета, номер домена : 10.1017/CBO9780511542985 , ISBN. 0-521-82758-2 , МР 2051713

[gm-2] Голумбик, Мартин С .; Монма, Клайд Л. (1982), «Обобщение интервальных графов с допусками», Труды тринадцатой Юго-восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1982), Congressus Numerantium , 35 : 321–331 , МР 0725892

[gc-3] Jump up to: ^а ^б «Графкласс: толерантность» , Информационная система по классам графов и их включениям , получено 30 сентября 2019 г.

[gmt-4] Голумбик, Мартин Чарльз ; Монма, Клайд Л.; Троттер, Уильям Т. младший (1984), «Графики допусков», Discrete Applied Mathematics , 9 (2): 157–170, doi : 10.1016/0166-218X(84)90016-7 , MR 0761599

[msz-5] Мерциос, Джордж Б.; Или Игнатий; Закс, Шмуэль (2011), «Распознавание толерантности и ограниченных графов толерантности» (PDF) , SIAM Journal on Computing , 40 (5): 1234–1257, doi : 10.1137/090780328 , MR 28545711

[1]

[2]

[3]

[4]

[5]