2-аппроксимационный алгоритм для задачи с вершинами-вершинами с использованием «Spanning Tree»

Я видел вопрос о 2-аппроксимационном алгоритме для проблемы с вершинным покрытием (VC, известная проблема Np-Complete), и я не знаю, ответ. Проблема заключается в следующем: Найдите 2-аппроксимационный алгоритм для проблемы с вершиной с использованием «Spanning Tree». Ну, многие жадные подходы уже представлены для VC, но специальный алгоритм с использованием «Spanning Tree» является сложным. Любая идея?2-аппроксимационный алгоритм для задачи с вершинами-вершинами с использованием «Spanning Tree»

источник

2011-01-31 parsa rastegari

Для теоретической информатики (http://cstheory.stackexchange.com/) существует отдельная сводка для стека. Вы можете лучше ответить на свой вопрос. –

О, Спасибо за ваше примечание. Я сделал это сейчас. –

Да, это не исследование, я изучаю алгоритмы для конкуренции, а иногда мне нужна помощь. Разве никто не знает ответа? Есть идеи? –

Вы просто ищете максимальное совпадение в заданном графе, а решение - это набор узлов, которые создают максимальное совпадение.

источник

2011-02-01 17:51:31 ShaQ

Можете ли вы рассказать об этом? Как вы получаете от набора ребер к набору вершин? – templatetypedef

Итак, так: Max Matching дает вам множество ребер, которые гарантируют, что каждая вершина связана с ребром только с одной другой вершиной или без вершин. Этот набор вершин (из ребер, включенных в макс совпадение) дает вам также ответ на проблему VC, но его 2-приближение приводит к тому, что в худшем случае вы можете выбрать в два раза больший набор вершин, чем оптимальный. – ShaQ

2-аппроксимационный алгоритм для задачи с вершинами-вершинами с использованием «Spanning Tree»

ответ

Смежные вопросы