Википедия

Задача о вершинном покрытии: различия между версиями

Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
Следующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
← Новая страница: «В Информатике, задача '''о вершинном покрытии''' является [[NP-полна...»
 
Нет описания правки
Строка 26:
Поскольку задача о вершинном покрытии является [[NP-полная задача|NP-полной ]] (NP-полнота может быть доказана сведением к [[Задача о клике| задаче о клике]].), то, к сожалению не существует эфективных алгоритмов для её точного решения. Несмотря на это существуют алгоритмы дающие "приближённое" решение этой задачи — можно найти вершинное покрытие, в котором число вершин не более чем вдвое превосходит минимально возможное.
 
== Смотри такжеЛитература ==
 
* [[covering (graph theory)]]
* [* {{книга
* {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979|title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | id = ISBN 0-7167-1045-5}} A1.1: GT1, pg.190.
|автор = Томас Х. Кормен и др.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 35.1, pp.1024—1027.
|часть = '''Глава 16. Жадные алгоритмы'''
|заглавие = Алгоритмы: построение и анализ
|оригинал = INTRODUCTION TO ALGORITHMS
|ссылка =
|издание = 1-е изд
|место = М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
|год = 2001
|страницы = 866
|isbn = 0-07-013151-1
}}
 
 
Источник — https://ru.wikipedia.org/wiki/Задача_о_вершинном_покрытии