Реоптимізація 2-критеріальної задачі про мінімальне вершинне покриття графа

Abstract

Вивчається ефект додавання множини з h = O(log n) вершин з деякими інцидентними ребрами до довільного екземпляра 2-критеріальної задачі про мінімальне вершинне покриття на оптимальний розв’язок.

Изучается эффект добавления множества из h = O(log n) вершин с некоторыми инцидентными ребрами к произвольному экземпляру 2-критериальной задачи о минимальном вершинном покрытии на оптимальное решение.

We study the effect of adding a set of h = O(log n) vertices incident with some edges to an arbitrary instance of 2-objective problem of minimum vertex cover on the optimal solution.