Tolerance graph

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. 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.

Every interval graph is a tolerance graph. The complement graph of every tolerance graph is a perfectly orderable graph, from which it follows that the tolerance graphs themselves are perfect graphs. It is NP-complete to determine whether a given graph is a tolerance graph. 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.

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. 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.

Every interval graph is a tolerance graph. The complement graph of every tolerance graph is a perfectly orderable graph, from which it follows that the tolerance graphs themselves are perfect graphs. It is NP-complete to determine whether a given graph is a tolerance graph. 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.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1329691591 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001329691591 · captured 1766838813.0 · version history

Cite this page as: encyclopegia.org, “Tolerance graph”, snapshot enwiki-001329691591. https://encyclopegia.org/a/tolerance-graph

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.