минимальных доминирующего набор ориентированного графа

Question

http://en.wikipedia.org/wiki/Dominating_set

Теперь у меня есть идея, чтобы найти его, и мне нужно ваше мнение

Первого:
Создание системы ранга на графике, каждая вершина имеет ранг. ранг вершины равен:
2 * [количество затраченных краев] - [число в-кромками]

Второе:
Alter алгоритм DFS: сделать это также вернуть группу всех корней на остовного леса (не изменяет сложность)

алгоритм:
1. старт со всеми вершинами, как минимальный набор доминирующая
2. запустить DFS со стартовой вершины: самый высокий рейтинг вершины
3. Посмотрите на корень в охватывающем лесу, возьмите список минимального доминирующего набора и удалите каждую вершину, которая не является корнем на курорте nning леса
4. Повторите 2-3 со следующим самым высоким рейтингом вершины который остался на минимальном доминировании установить
5. стоп, когда вы запускали ДФС на каждой вершине по минимальному доминированию установить
6. Возвращение его

Я использую adj-list, поэтому DFS - O (| V | + | E |) Что вы думаете об этом алгоритме? это будет работать? могу ли я лучше? Каков амортизированный наихудший случай этого алгоритма?

Answer 1

Будет ли это работать?

No. Простой контрпример этот график:

ранги [1:6, 2:-1, 3:1, 4:-1, 5:-1]. На шаге 2 вы запускаете DFS от вершины 1. Это единственный корень остовного леса, так на шаге 3 вы удаляете каждую другую вершину и возвращаетесь. Однако это не доминирующий набор! 5 не находится ни внутри, ни рядом с узлом в доминирующем наборе.

Что такое амортизированный наихудший случай этого алгоритма?

Худший случай: O (| V | + | E | + k), где k - размер возвращаемого набора. Вы удалите все, кроме корней, в первый раз, так что следующее время O (k) через цикл будет принимать только время O (k).

Могу ли я лучше?

Да, как по правильности, так и по скорости. Удалите всех соседей текущей вершины, а затем перейдите к следующей вершине, все еще находящейся в наборе. Это займет только O (| V | + | E |).

Кажется, что вы пытались получить то, что более близко приближается к глобальному минимуму; для этого я рекомендую проверить литературу для «Минимальной аппроксимации минимального уровня».