Чтобы найти минимальный доминирующий набор неориентированного графа G с V узлами, вы можете использовать эвристический алгоритм, подобный этому:
- Первоначально доминирующий набор пуст, D: 0.
- Во время алгоритма множество D растет по «ленивому» принципу, то есть увеличивает D до
возможно.
- Для каждой вершины v в V мы сохраняем число CovCnt [v], которое является количеством раз, когда вершина покрыта оставшимися вершинами.
- Мы предполагаем, что v смежна с собой
- CovCnt [v] инициализируется как deg [v] + 1, где deg [v] обозначает степень v.
- Мы также оцениваем «важность» v, применяя специальную стратегию скоринга для ранжирования вершин как потенциальных центров.
- Первоначально оценка вершины равна счетчику покрытия, чтобы отразить эмпирическое правило, что сначала нужно проверять вершины с низкими градусами.
- Затем на каждом шаге проверяется вершина x с минимальным счетом, т.е.
- Если есть смежная вершина с числом покрытия 1, то x добавляется к D; Если это так, вершина x является единственно возможной оставшейся вершиной в графе, которая может покрыть такого соседа. Следовательно, x должен быть добавлен к текущему доминирующему набору D. Для счетчиков покрытия всех соседей x установлено значение 0, чтобы обозначить их как покрытые
- в противном случае x используется для уменьшения счетчиков покрытия и увеличения баллов еще не покрытых смежных вершин.
Я использовал этот алгоритм из здесь
У меня такой вопрос: как я могу изменить его для использования в ориентированном графе?