Hispanopedia WikiEn teoría de grafos , un grafo de tolerancia es un grafo no dirigido en el que cada vértice puede representarse mediante un intervalo cerrado y un número real llamado su tolerancia, de tal manera que dos vértices son adyacentes en el grafo siempre que sus intervalos se superpongan en una longitud que sea al menos el mínimo de sus dos tolerancias. [1] Esta clase de grafos fue introducida en 1982 por Martin Charles Golumbic y Clyde Monma, quienes los utilizaron para modelar problemas de programación en los que las tareas a modelar pueden compartir recursos durante cantidades limitadas de tiempo. [2]
Todo gráfico de intervalo es un gráfico de tolerancia. [3] El gráfico complementario de cada gráfico de tolerancia es un gráfico perfectamente ordenable , de lo que se deduce que los propios gráficos de tolerancia son gráficos perfectos . [4]
Es NP-completo determinar si un gráfico dado es un gráfico de tolerancia. [5] Sin embargo, debido a que los gráficos de tolerancia son gráficos perfectos, muchos problemas algorítmicos que son difíciles para otras clases de gráficos, incluida la coloración de gráficos y el problema de la camarilla , se pueden resolver en tiempo polinomial en gráficos de tolerancia. [3]
Referencias
- ^ Golumbic, Martin Charles ; Trenk, Ann N. (2004), Gráficos de tolerancia , Cambridge Studies in Advanced Mathematics, vol. 89, Cambridge University Press, doi :10.1017/CBO9780511542985, ISBN 0-521-82758-2, Sr. 2051713
- ^ Golumbic, Martin C. ; Monma, Clyde L. (1982), "Una generalización de gráficos de intervalos con tolerancias", Actas de la decimotercera conferencia del sudeste sobre combinatoria, teoría de grafos y computación (Boca Raton, Fla., 1982), Congressus Numerantium , 35 : 321–331, MR 0725892
- ^ ab "Graphclass: tolerancia", Sistema de información sobre clases de grafos y sus inclusiones , consultado el 30 de septiembre de 2019
- ^ Golumbic, Martin Charles ; Monma, Clyde L.; Trotter, William T. Jr. (1984), "Gráficos de tolerancia", Discrete Applied Mathematics , 9 (2): 157–170, doi : 10.1016/0166-218X(84)90016-7 , MR 0761599
- ^ Mertzios, George B.; Sau, Ignasi; Zaks, Shmuel (2011), "El reconocimiento de la tolerancia y los gráficos de tolerancia acotada" (PDF) , SIAM Journal on Computing , 40 (5): 1234–1257, doi :10.1137/090780328, MR 2854571
