기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
제한된 분지수를 가지는 최소지름 신장트리
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • 제한된 분지수를 가지는 최소지름 신장트리
저자명
안희갑,신찬수
간행물명
정보과학회논문지. Journal of KIISE. 시스템 및 이론
권/호정보
2004년|31권 1호|pp.78-85 (8 pages)
발행정보
한국정보과학회
파일정보
정기간행물|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

이차원 평면에 주어진 n개의 점을 연결하는 신장트리(spanning tree) 중에서, 지름이 최소가 되는 트리는 특정 점에서의 분지수(degree)가 n-1까지 증가할 수 있다. 신장트리가 실제 네트워크 구조로 사용된다면 높은 분지수를 갖는 노드에선 작업 집중현상이 발생하여 전체 네트워크의 성능을 저하시킬 수 있다. 따라서 작은 분지수와 작은 지름을 갖는 트리를 구성하는 것은 중요하다. 본 논문에서는 (1) 트리의 분지수를 자유롭게 조정할 수 있고, (2) 트리의 지름이 최소 지름보다 상수 배 이상 크지 않고, (3) 임의의 점을 루트로 정하여 트리를 구하더라도 항상 단조(monotone)하며, (4) 트리의 에지들이 서로 교차하지 않는 신장트리 구성 알고리즘을 제안한다. 여기서 트리가 단조하다는 것은 루트부터 시작하여 임의의 노드까지 연결되는 경로 위에 있는 점은 루트로부터의 유클리디언 거리가 단순 증가하는 것을 의미한다. 이 단조성은 신장트리를 가시화 할 때의 중요한 미적 기준으로 사용될 수 있다.

기타언어초록

Given a set S of n points in the plane, a minimum-diameter spanning tree(MDST) for the set might have a degree up to n-1. This might cause the degradation of the network performance because the node with high degree should handle much more requests than others relatively. Thus it is important to construct a spanning tree network with small degree and diameter. This paper presents an algorithm to construct a spanning tree for S satisfying the following four conditions: (1) the degree is controled as an input, (2) the tree diameter is no more than constant times the diameter of MDST, (3) the tree is monotone (even if arbitrary point is fixed as a root of the tree) in the sense that the Euclidean distance from the root to any node on the path to any leaf node is not decreasing, and (4) there are no crossings between edges of the tree. The monotone property will play a role as an aesthetic criterion in visualizing the tree in the plane.