K-Closure of a graph

Материал из WikiGrapp
Перейти к:навигация, поиск

\,k-Closure of a graph\,k-Замыкание графа.

The \,k-closure \,G_{k}(G) of a graph \,G is obtained from \,G by recursively joining pairs of non-adjacent vertices whose degree-sum is at least \,k until no such pair remains. It is known that if \,G_{n}(G) is complete, then \,G contains a Hamiltonian cycle. The \,k-closure of a graph can be computed in {\mathcal O}(n^{3}) time in the worst case.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.