グラフ理論において、許容グラフとは、すべての頂点が閉区間とその許容値と呼ばれる実数で表すことができる無向グラフであり、2つの頂点の区間が少なくとも2つの許容値の最小値の長さで重なり合う場合、それらの頂点はグラフ内で隣接している。[1]このクラスのグラフは、1982年にマーティン・チャールズ・ゴルムビックとクライド・モンマ によって導入され、モデル化されるタスクが限られた時間内にリソースを共有できるスケジューリング問題をモデル化するために使用された。 [2]
あらゆる区間グラフは許容グラフである。[3]あらゆる許容グラフの補グラフは完全に順序付け可能なグラフであり、そこから許容グラフ自体も完全グラフであることが分かる。[4]
与えられたグラフが許容グラフであるかどうかを判断することはNP完全である。 [5]しかし、許容グラフは完全グラフであるため、グラフの色付けやクリーク問題 など、他のグラフのクラスでは難しい多くのアルゴリズムの問題が、許容グラフでは多項式時間で解くことができる。[3]
参考文献
- ^ ゴルムビック、マーティン・チャールズ、トレンク、アン・N.（2004）、許容グラフ、ケンブリッジ高等数学研究、第89巻、ケンブリッジ大学出版局、doi：10.1017 / CBO9780511542985、ISBN 0-521-82758-2、MR 2051713
- ^ Golumbic, Martin C. ; Monma, Clyde L. (1982)、「許容誤差を伴う区間グラフの一般化」、Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Florida, 1982)、Congressus Numerantium、35 : 321– 331、MR 0725892
- ^ ab "Graphclass: tolerance",グラフクラスとその包含に関する情報システム, 2019年9月30日閲覧
- ^ ゴルムビック、マーティン・チャールズ；モンマ、クライド・L.；トロッター、ウィリアム・T.・ジュニア（1984）「許容グラフ」、離散応用数学、9（2）：157–170、doi：10.1016/0166-218X（84）90016-7、MR 0761599
- ^ Mertzios, George B.; Sau, Ignasi; Zaks, Shmuel (2011)、「許容誤差と境界付き許容誤差グラフの認識」(PDF)、SIAM Journal on Computing、40 (5): 1234– 1257、doi :10.1137/090780328、MR 2854571
