- 차수 3인 트리에서 가장 긴 비음수 경로를 찾는 알고리즘
- ㆍ 저자명
- 김성권
- ㆍ 간행물명
- 정보과학회논문지. Journal of KIISE. 시스템 및 이론
- ㆍ 권/호정보
- 2004년|31권 7호|pp.397-401 (5 pages)
- ㆍ 발행정보
- 한국정보과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
각 에지에 무게(양수, 음수, 0 가능)가 주어진 트리에서, 경로의 에지들의 무게의 합이 비음수이면서 길이가 가장 긴 경로를 구하는 문제를 해결하고자 한다. 차수가 3인 트리에서 가장 긴 비음수 경로를 찾는 Ο(n log n) 시간 알고리즘을 제시한다. n은 트리가 가지는 노드의 수이다.
In an edge-weighted(positive, negative, or zero weights are possible) tree, we want to solve the problem of finding a longest path such that the sum of the weights of the edges in the path is non-negative. We present an algorithm to find a longest non-negative path of a degree 3 tree in Ο(n log n) time, where n is the number of nodes in the tree.