여러 루트 버텍스가있는 그래프의 최소 스패닝 트리

Question

모든 루트 버텍스 사이에 루트 버텍스 집합이 주어지면 유향 그래프에서 최소 스패닝 트리 (최적의 분기)를 계산하는 알고리즘이 있는지 알고 싶습니다. 하나의 루트 꼭지점뿐만 아니라 그래프의 다른 모든 꼭지점도 포함됩니다.

...을 algorighm 녹색 하위처럼 뭔가를 반환해야합니다 :

루트 정점 [1,4,6] 다음 그림에 같은 그래프 G의 집합을 감안할 때 - 같은 그림에 대한 그림.

알고리즘에 제공된 모든 루트 정점을 연결하는 MST를 얻고 싶습니다. 나는-될 알고리즘의 결과가 모든 루트 정점과 다른 정점 G.

에서

사항이 포함 된 그래프 G의 서브 그래프이라고 생각하는 경향이 :

1. 내가 알고이 는 직접 그래프의 MST가 아니지만 Chu–Liu/Edmonds algorithm입니다.
2. 그런 알고리즘의 결과 (실제로 가능한 경우)는 모든 루트 정점과 함께 그래프의 일부 정점을 포함하는 최적의 분기를 반환합니다.

Answer 1

최소 스패닝 트리가 모든 정점에 걸쳐 있다고 가정합니다. 문제가있는 Steiner Tree을 실제로 다룰 수 있다고 생각합니다. 그 중 일부만 연결하면됩니다. 불행히도, 방향이없는 가장자리를 가진 전통적인 Steiner 트리 문제는 이미 NP 완료이므로 당신보다 앞서 어려운 길을가집니다.