Русская Википедия:Гамильтоново дополнение
Задача гамильтонова дополнения — это задача нахождения минимального числа рёбер, которое нужно добавить в граф, чтобы он стал гамильтоновым.
Ясно, что задача в общем случае NP-трудна (поскольку её решение даёт ответ на NP-полную задачу определения, имеет ли граф гамильтонов цикл). Связанная задача разрешимости, может ли добавление K рёбер в заданный граф дать гамильтонов граф, является NP-полной.
Более того, Ву, Лу и Ли показали, что существование эффективных алгоритмов с постоянным коэффициентом аппроксимации для этой задачи маловероятноШаблон:Sfn.
Задача может быть решена полиномиальное время для некоторых классов графов, куда входят параллельно-последовательные графыШаблон:Sfn и их обобщенияШаблон:Sfn, которые включают внешнепланарные графы. В эти классы входят также рёберные графы деревьевШаблон:SfnШаблон:Sfn и кактусыШаблон:Sfn.
Гамарник и Свириденко использовали алгоритм линейного времени для решения задачи на деревьях для изучения асимптотического числа рёбер, которые нужно добавить к разреженным случайным графам, чтобы сделать их гамильтоновымиШаблон:Sfn.
Примечания
Литература
- Шаблон:Статья
- Шаблон:КнигаШаблон:Недоступная ссылка
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
