Что такое алгоритм для нахождения схемы с максимальным весом в ориентированном графе?

Question

Первая проблема заключалась в том, что я не мог найти алгоритм, который при заданном ориентированном графе в качестве ввода дает в качестве вывода список всех циклов, присутствующих на графике. (Эта проблема должна быть NP-полной).

После некоторого размышления о проблеме я понял, что, вероятно, мне действительно нужно было найти схему (она может иметь повторяющуюся вершину, но не дублировать края) с максимальным весом (суммой весов ребер).

Это тоже проблема с NP-полным, и способ продолжения может состоять в том, чтобы перечислить все схемы, присутствующие на графике, а затем отсортировать их по сумме весов ребер.

Знаете ли вы какой-то алгоритм, который дает в качестве вывода список всех схем, присутствующих в , ориентированных на график? Или тот, который находит схему с максимальным весом?

Я нашел это, но это не совсем то, что мне нужно.

http://epubs.siam.org/doi/abs/10.1137/0205007

Однако вы подтверждаете вычислительную сложность этих проблем?

Answer 1

Вы могли бы сделать sth. как здесь: Finding all cycles in a directed graph.

Вы выполняете поиск по каждому узлу и распараллеливаете его, чтобы сократить время выполнения. Затем вы применяете эффективный алгоритм сортировки к вашему списку циклов, где каждый цикл представляет собой список узлов. Сортировочные алгоритмы могут мне, например, Mergesort или Quicksort, но выбирайте, что когда-либо предпочитаете.

Надеюсь, что это приведет вас вперед.