• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Эффективное вычисление допусков в задаче о взвешенном независимом множестве для некоторых классов графов

Понятие допуска элемента оптимального решения часто используется для анализа устойчивости оптимального решения в задачах комбинаторной оптимизации и служит основой для разработки переборных алгоритмов, решающих эти задачи. В данной работе показывается, что для задачи о взвешенном независимом множестве и двудольного графа с n вершинами и m рёбрами оптимальное решение вычисляется за время O(nm), а все допуски относительно него за время O(n^2). Приводится алгоритм, определяющий для интервального графа с n вершинами и m рёбрами и оптимальное взвешенное независимое множество и все соответствующие допуски за время O(n+m)ю