한국정보통신학회 논문지 (Journal of the Korea Institute of Information and Communication Engineering)
Current Result Document : 5 / 32
이전건
다음건 
| 한글제목(Korean Title) |
그래프의 정점 연결성에 대한 최소 범위 할당 |
| 영문제목(English Title) |
Minimum Cost Range Assignment for the Vertex Connectivity of Graphs |
| 저자(Author) |
이원희
강보윤
김윤정
김현경
박정규
박수이
Won-hee Lee
Bo-yun Kang
Yoon-jung Kim
Hyun-kyung Kim
Jung Kyu Park
Su E Park
김재훈
Jae-Hoon Kim
|
| 원문수록처(Citation) |
VOL 21 NO. 11 PP. 2103 ~ 2108 (2017. 11) |
한글내용
(Korean Abstract) |
m차원 평면 R^m상에 n개의 점들 pi가 주어질 때, 범위 R에 대해서, 점 pi로부터 거리 r 이내 점들의 집합 Ti를 생각한다. m=1일 때, Ti는 직선상의 구간이고, m=2 일 때, Ti는 평면상의 원에 해당된다. 집합 Ti들을 정점에 대응하고, 두 집합이 교차하는 경우에 대응하는 두 정점 사이에 간선을 연결하면 교차 그래프 G를 얻을 수 있다. m=1일 때, G는 진구간 그래프 (proper intercal graph), m=2일 때, G는 단위 원판 그래프 (unit disk graph)라고 부른다. 본 논문에서는 범위 r이 변화하면 바뀌는 교차 그래프 G(r)에 관심이 있다. 특별히 G(r)가 연글 그래프가 되는 최소 r을 찾는 문제를 다룰 것이다. 이 문제에 대해서 진구간 그래프 G(r)에 대해서 O(n) 시간 알고리즘, 단위 원판 그래프 G(r)에 대해서 O((n^2)logn)시간 알고리즘을 제안한다. 직선상의 점들이 추가되거나 삭제되는 동적 환경 하에서 위 문제를 O(logn)시간에 해결하는 알고리즘도 제안한다
|
영문내용
(English Abstract) |
For n points pi on the m-dimensional plane R^m and a fixed range r, consider a set Ti containing points the distances from pi of which are less than or equal to r. In case m=1, Ti is an interval on a line, it is a circle on a plane when m=2. For the vertices corresponding to the sets Ti, there is an edge between the vertices if the two sets intersect. Then this graph is called an intersection graph G. For m=1, G is called a proper interval graph and for m=2, it is called an unit disk graph. In this paper, we are concerned in the intersection graph G(r) when r changes. In particular, we consider the problem to find the minimum r such that G(r) is connected. For this problem, we propose an O(n) algorithm for the proper interval graph and an O(n^2logn) algorithm for the unit disk graph. For the dynamic enviroment in which the points on line are added or deleted, we give an O(logn) algorithm for the problem.
|
| 키워드(Keyword) |
노인 운동
모션 인식
키넥트
홈 트레이닝
Excersice for the elderly
Home Training
Kinect
Motion Recognition
교차 그래프
단위 원판 그래프
동적 환경
정점 연결성
진구간 그래프
Dynamic Environment
Intersection Graph
Proper Interval Graph
Unit Disk Graph
Vertex Connectivity
|
| 파일첨부 |
PDF 다운로드
|
