- 트리에서 길이 제한이 있는 가장 무거운 경로를 찾는 알고리즘
- ㆍ 저자명
- 김성권,Kim. Sung-Kwon
- ㆍ 간행물명
- 정보처리학회논문지. The KIPS transactions. Part A. Part A
- ㆍ 권/호정보
- 2006년|6호|pp.541-544 (4 pages)
- ㆍ 발행정보
- 한국정보처리학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
에지마다 길이와 무게(둘 다 양수, 음수, 0 가능)가 주어진 트리에서, 길이의 합이 주어진 값 이하이면서 무게의 합이 가장 큰 경로를 찾는 O(nlognloglogn) 시간 알고리즘을 제시한다. 이전의 결과 O($nlog^2n$) 보다 향상된 것이다. 여기서, n은 트리가 가지는 노드의 수이다.
In a tree with each edge associated with a length and a weight (positive, negative, or zero are possible) we develop an O(nlognloglogn) time algorithm for finding a path such that its sum of weights is maximized and its sum of lengths does not exceed a given value. The previously best-known result is O($nlog^2n$), where n is the number of nodes in the tree.