Content deleted Content added
Bluelinking 1 books for verifiability.) #IABot (v2.1alpha3 |
m →Algorithms: Orthography: I changed "provably" to "probably". |
||
Line 32:
==Algorithms==
A transitive orientation of a graph, if it exists, can be found in linear time.<ref>{{harvtxt|McConnell|Spinrad|1997}}; see {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 91.</ref> However, the algorithm for doing so will assign orientations to the edges of any graph, so to complete the task of testing whether a graph is a comparability graph, one must test whether the resulting orientation is transitive, a problem
Because comparability graphs are perfect, many problems that are hard on more general classes of graphs, including [[graph coloring]] and the [[independent set problem]], can be computed in polynomial time for comparability graphs.
| |||