Content deleted Content added
move images around and add one |
Algorithmic aspects |
||
Line 62:
==Self-complementary graphs and graph classes==
[[File:Self-complementary NZ graph.svg|thumb|upright=0.
{{main|Self-complementary graph}}
Line 97:
| volume = 52
| year = 2006}}.</ref>
==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
| doi = 10.1016/S0020-0190(98)00071-4
| issue = 4
| journal = [[Information Processing Letters]]
| mr = 1629714
| pages = 209–213
| title = Linear time algorithms for graph search and connectivity determination on complement graphs
| volume = 66
| year = 1998}}.</ref><ref>{{citation
| last1 = Kao | first1 = Ming-Yang
| last2 = Occhiogrosso | first2 = Neill
| last3 = Teng | first3 = Shang-Hua | author3-link = Shang-Hua Teng
| doi = 10.1023/A:1009720402326
| issue = 4
| journal = Journal of Combinatorial Optimization
| mr = 1669307
| pages = 351–359
| title = Simple and efficient graph compression schemes for dense and complement graphs
| volume = 2
| year = 1999}}.</ref>
==References==
| |||