유향 그래프에서 최대 가중치를 가진 회로를 찾는 알고리즘은 무엇입니까?

Question

첫 번째 문제는 지시 그래프를 입력으로 주어진 그래프에있는 모든 사이클의 목록을 출력으로 제공하는 알고리즘을 찾을 수 없다는 것이 었습니다. (이 문제는 NP 완성이어야합니다).

잠시 동안 문제에 대해 생각한 후, 아마도 내가 정말로 필요로하는 것은 최대 무게 (가장자리 무게의 합)로 회로 (중복 버텍스를 가질 수는 있지만 중복 된 가장자리는 가질 수 없음)를 찾는 것임을 깨달은 것입니다.

또한 NP 완성 문제 여야하며 진행 방법은 그래프에있는 모든 회로를 나열한 다음 에지 가중치의 합으로 정렬하는 것입니다.

출력으로 그래프에있는 모든 회로의 목록을 제공하는 알고리즘을 알고 있습니까? 또는 최대 무게의 회로를 찾는 사람?

나는 이것을 발견했지만, 정확히 내가 필요한 것은 아니다.

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

그러나 이러한 문제의 복잡도를 확인합니까?

Answer 1

당신은 할 수 있습니다. 여기처럼 : Finding all cycles in a directed graph.

모든 노드에 대해이 검색을 수행하고이를 병렬 처리하여 런타임을 줄입니다. 이후에 각주기가 노드 목록 인 순환 목록에 효율적인 정렬 알고리즘을 적용합니다. 정렬 알고리즘은 예를 들어 Mergesort 나 Quicksort 일지 모르지만 선호하는 것을 선택하십시오 ..

나는 앞으로 나아갈 수 있기를 바랍니다.