트리에서 지배 집합을 찾는 다항식 시간 알고리즘

Question

G = (V, E)를 무향 그래프로 둡니다. 모든 v ∈ V에 대해 v∈ S를 가지거나 (u, v) ∈ E와 같은 어떤 노드 u ∈ S가있는 경우, G의 노드들의 부분 집합 S ⊆ V는 "우위 집합"이라 불린다. V의 노드는 S의 어떤 노드에 가장자리로 연결된다. V의 노드에서 비 음의 가중치 w (v)가 주어지면 목표는 G에서 최소 가중 지배 집합을 찾는 것이다. (주 :이 문제는 G가 트리 일 때 POLYNOMIAL 시간 알고리즘을 설계해야합니다.

위키에 대한 Steiner tree 문제에 대해 읽었습니다. 다소 관련이 있지만 여전히 혼란 스럽습니다.

어떻게해야합니까?

Answer 1

19 페이지에있는 트리의 버텍스 에지 가중치 제어 번호에 대한 동적 프로그래밍 알고리즘을 제공하는이 백서를 발견했습니다. "트리 순서화"의 경우 순차 정렬 순회를 사용할 수 있습니다. 조금 수정해야합니다 (예 : 모든 에지 가중치를 0으로 설정). DP 매트릭스에서 솔루션을 구성하는 방법을 찾아야합니다. 희망이 도움이됩니다.

http://www.math.ntu.edu.tw/~mathlib/preprint/2011-01.pdf