근사 알고리즘/Network design (1) 썸네일형 리스트형 슈타이너 트리 2-근사 알고리즘 (2-Approximation for Steiner Tree) 코스워크가 모두 끝난 요즘 과거에 제대로 이해하지 못했거나 미처 보지 못하고 넘어간 것들을 제대로 공부해 보고자 교과서를 처음부터 다시 보고 있습니다. 공부하는 중에 개인적으로 정리도 할 겸 공유할 만한 내용이 있으면 포스팅을 하고자 합니다. 이번에 다룰 문제는 슈타이너 트리 문제(Steiner tree problem)입니다. 이 문제는 잘 알려진 최소 스패닝 트리 문제(minimum spanning tree problem, MST)의 일반화된 문제입니다. MST는 크루스칼 알고리즘(Kruskal's algorithm)이나 프림 알고리즘(Prim's algorithm) 등을 활용하여 다항 시간에 해결할 수 있다는 것이 잘 알려져 있습니다. 하지만 슈타이너 트리 문제는 NP-난해(NP-hard)하다고 알려.. 이전 1 다음
