Content deleted Content added
→Definition: in terms of the adjacency matrix |
Dokidaki-ylc (talk | contribs) mNo edit summary |
||
Line 85:
==Algorithmic aspects==
In the [[analysis of algorithms]] on graphs, the distinction between a graph and its complement is an important one, because a [[sparse graph]] (one with a small number of edges compared to the number of pairs of vertices) will in general not have a sparse complement, and so an algorithm that takes time proportional to the number of edges on a given graph may take a much larger amount of time if the same algorithm is run on an explicit representation of the complement graph. Therefore, researchers have studied algorithms that perform standard graph computations on the complement of an input graph, using an [[implicit graph]] representation that does not require the explicit construction of the complement graph. In particular, it is possible to simulate either [[depth-first search]] or [[breadth-first search]] on the complement graph, in an amount of time that is linear in the size of the given graph, even when the complement graph may have a much larger size.<ref name="iy98"/> It is also possible to use these simulations to compute other properties concerning the connectivity of the complement graph.<ref name="iy98">{{citation
| last1 = Ito | first1 = Hiro
| last2 = Yokoyama | first2 = Mitsuo
| |||