Tolerance graph

In graph theory, a tolerance graph is an undirected graph in which every vertex can be represented by a closed interval and a real number called its tolerance, in such a way that two vertices are adjacent in the graph whenever their intervals overlap in a length that is at least the minimum of their two tolerances.[1] This class of graphs was introduced in 1982 by Martin Charles Golumbic and Clyde Monma, who used them to model scheduling problems in which the tasks to be modeled can share resources for limited amounts of time.[2]

Every interval graph is a tolerance graph.[3] The complement graph of every tolerance graph is a perfectly orderable graph, from which it follows that the tolerance graphs themselves are perfect graphs.[4]

It is NP-complete to determine whether a given graph is a tolerance graph.[5] However, because tolerance graphs are perfect graphs, many algorithmic problems that are hard on other classes of graphs, including graph coloring and the clique problem, can be solved in polynomial time on tolerance graphs.[3]

References

  1. ^ Golumbic, Martin Charles; Trenk, Ann N. (2004), Tolerance graphs, Cambridge Studies in Advanced Mathematics, vol. 89, Cambridge University Press, doi:10.1017/CBO9780511542985, ISBN 0-521-82758-2, MR 2051713
  2. ^ Golumbic, Martin C.; Monma, Clyde L. (1982), "A generalization of interval graphs with tolerances", Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), Congressus Numerantium, 35: 321–331, MR 0725892
  3. ^ a b "Graphclass: tolerance", Information System on Graph Classes and their Inclusions, retrieved 2019-09-30
  4. ^ Golumbic, Martin Charles; Monma, Clyde L.; Trotter, William T. Jr. (1984), "Tolerance graphs", Discrete Applied Mathematics, 9 (2): 157–170, doi:10.1016/0166-218X(84)90016-7, MR 0761599
  5. ^ Mertzios, George B.; Sau, Ignasi; Zaks, Shmuel (2011), "The recognition of tolerance and bounded tolerance graphs" (PDF), SIAM Journal on Computing, 40 (5): 1234–1257, doi:10.1137/090780328, MR 2854571

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.