논문KCI 등재
트리에서 길이 제한이 있는 가장 무거운 경로를 찾는 알고리즘
Algorithm for finding a length-constrained heaviest path of a tree
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
주제분류컴퓨터학
초록
에지마다 길이와 무게(둘 다 양수, 음수, 0 가능)가 주어진 트리에서, 길이의 합이 주어진 값 이하이면서 무게의 합이 가장 큰 경로를 찾는 시간 알고리즘을 제시한다. 이전의 결과 보다 향상된 것이다. 여기서, 은 트리가 가지는 노드의 수이다.
Abstract
Abstract: In a tree with each edge associated with a length and a weight (positive, negative, or zero are possible) we develop an 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 , where is the number of nodes in the tree.
참고문헌 (3)
- "Fundamentals of Data Structures in C" (1993), Computer Science Press
- "Fast parallel algorithm for finding k-th longest path in a tree", pp.164~169 (1997)
- "An efficient algorithm for the length-constrained heaviest path problem on a tree", 69, pp.63~67 (1999)
관련 논문AI추천
구간 그래프상의 최대 가중치 독립 집합 문제를 위한 효율적인 알고리즘강장하공학기술연구원 · 공학기술논문지2015 · 제8권 제1호평균 지연 시간과 트래필 용량이 제한되는 스패닝 트리 문제의 2단계 휴리스틱 알고리즘이용진한국정보처리학회 · 정보처리학회논문지C2003 · 제10권 제3호극대 증가 부분서열을 찾는 선형 알고리즘나중채(사)한국스마트미디어학회 · 스마트미디어저널2023 · 제12권 제6호경로 압축을 이용한 DJ 그래프의 지연 감축 알고리즘심손권, 안회학한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2002 · 제9권 제2호최소 기대 부하량을 이용한최단경로 탐색 알고리즘 개발유영근한국ITS학회 · 한국ITS학회 논문지2013 · 제12권 제5호선분상의 포탈을 이용한 근사 선분 최소 신장 트리의 생성김수인, 김인범한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2009 · 제16권 제6호
이 간행물의 다른 논문 (20건)
임베디드 시스템을 위한실시간 함수형 반응적 프로그램 변환기우균, 이동주pp. 481-488추론적 부분 중복 제거의 최적화 예외 영역문제 해결 알고리즘안희학, 신현덕pp. 489-494유비쿼터스 컴퓨팅 환경을 위한 에이전트 시스템과 인포메이션 버스 어댑터간 상호 운용성을 위한 기법한승욱, 윤희용, 박상용pp. 495-500자기 조직적 우수 피어 링 검색기법에서 입자 군집 최적화(PSO)를 이용한 적응적 우수 피어 비율 조절 기법장형근, 한세영, 박성용pp. 501-510데이터 그리드 환경에서 파일 교체 정책 연구박홍진pp. 511-516