슈타이너 트리의 양방향 컷 완화 정수성 간극
슈타이너 트리 문제는 네트워크 설계 분야의 핵심 난제 중 하나입니다. 이 문제는 주어진 가중치 그래프에서 특정 터미널 노드들을 모두 포함하는 최소 가중치 트리를 찾는 것을 목표로 합니다. 현재 알려진 최적 근사 알고리즘들은 많은 수의 후보 구성 요소를 열거해야 하므로 실제 적용에는 속도 제약이 있습니다. 이러한 한계를 극복하기 위해 양방향 컷 완화(BCR)가 유망한 대안으로 주목받고 있습니다. BCR은 모든 엣지를 양방향화하고 임의의 터미널을 루트로 설정한 뒤, 루트를 포함하지 않는 모든 컷에 대해 분수 엣지 흐름이 1단위가 되도…