본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

차수 3인 트리에서 가장 긴 비음수 경로를 찾는 알고리즘
Algorithm for Finding a Longest Non-negative Path in a Tree of Degree 3

김성권   (중앙대학교 컴퓨터공학과UU0001197  );
  • 초록

    각 에지에 무게(양수, 음수, 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.


  • 주제어

    비음수 경로 .   트리.  

  • 참고문헌 (6)

    1. D.E. Knuth, The Art of Programming, Vol. 1. Fundamental Algorithms, 2nd Edition, Addison-Wesley, 1973 
    2. L. Wang and Y. Xu, SEGID: Identifying interesting segments in (multiple) sequence alignments, Bioinformatics, vol. 19(2), pp. 297-298, 2003 
    3. B.Y. Wu, K.-M. Chao, and C.Y. Tang, An efficient algorithm for the length-constrained heaviest path problem on a tree, Information Processing Letters, vol. 69, pp. 63-67, 1999 
    4. L. Allison, Longest biased intervals and longest non-negative sum intervals, Bioinformatics, vol. 19(10), pp. 1294-1295, 2003 
    5. A.J. Goldman, Optimal center location in simple networks, Transportation Science, vol. 5, pp. 212-221, 1971 
    6. O. Kariv, S.L. Hakimi, An algorithmic approach to network location problem. I: The p-centers, SIAM Journal on Applied Mathematics, vol. 37, pp. 513-538, 1979 

 저자의 다른 논문

  • 김성권 (19)

    1. 2000 "전광 트리 네트워크에서 파장 및 경로설정 문제를 해결하는 알고리즘에 관한 연구" 정보처리논문지 = The transactions of the Korea Information Processing Society 7 (12): 3952~3963    
    2. 2000 "실용적이고 안전한 전자투표 프로토콜에 관한 연구" 通信情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology 10 (4): 21~32    
    3. 2000 "적은 굴곡점을 가진 이진트리를 그리는 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 27 (2): 209~215    
    4. 2000 "두개의 동일한 탐조등으로 볼록다각형을 비추는 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 27 (4): 416~419    
    5. 2001 "점 집합을 두 개의 부채꼴로 포함하는 알고리즘 개발" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 28 (6): 278~288    
    6. 2001 "디지털 컨텐츠의 지적 재산권 보호를 위한 익명 핑거프린팅의 연구 동향" 情報保護學會誌 = KIISC review 11 (3): 90~99    
    7. 2002 "인터넷 광고에서 안전하고 효율적인 측정방법" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 29 (3): 153~160    
    8. 2002 "단백질 시퀀스와 가중치 스트링에 대한 탐색 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 29 (8): 456~462    
    9. 2002 "크로스 링크된 단백질 서브시퀀스를 찾는 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 29 (9): 514~519    
    10. 2003 "이동통신 환경에서 임시 익명 아이디를 이용한 위치 불추적 서비스와 지불 프로토콜에 관한 연구" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 30 (2): 78~92    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기