Tolerance graph (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (en) |
| dbo:wikiPageID | 61928385 (xsd:integer) |
| dbo:wikiPageLength | 3176 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032195129 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Perfect_graphs dbr:Undirected_graph dbr:Clique_problem dbr:Graph_coloring dbr:NP-complete dbr:Martin_Charles_Golumbic dbr:Complement_graph dbr:Perfect_graph dbr:Graph_theory dbr:Closed_interval dbr:Interval_graph dbr:Polynomial_time dbr:Scheduling_(production_processes) dbr:Perfectly_orderable_graph |
| dbp:wikiPageUsesTemplate | dbt:R dbt:Reflist |
| dct:subject | dbc:Perfect_graphs |
| rdfs:comment | 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. (en) |
| rdfs:label | Tolerance graph (en) |
| owl:sameAs | wikidata:Tolerance graph https://global.dbpedia.org/id/BvQd9 |
| prov:wasDerivedFrom | wikipedia-en:Tolerance_graph?oldid=1032195129&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Tolerance_graph |
| is dbo:wikiPageWikiLink of | dbr:Ann_Trenk dbr:Perfectly_orderable_graph |
| is foaf:primaryTopic of | wikipedia-en:Tolerance_graph |