거리공간속 경로 그래프에 간선추가를 통한 지름의 최소화 (Minimizing the Diameter by Augmenting an Edge to a Path in a Metric Space)

서지정보

· 발행기관 : 한국정보통신학회
· 수록지 정보 : 한국정보통신학회논문지 / 26권 / 1호 / 128 ~ 133페이지
· 저자명 : 김재훈

초록

본 논문은 거리 공간(metric space) 속에 포함된 그래프에서 각 간선의 가중치가 거리 공간 상의 두 끝 정점간의 거리로 주어지는 그래프를 다룬다. 특별히 우리는 이러한 그래프 중 개 정점을 가진 경로 에 관해서 연구한다. 우리는 경로 에 하나의 간선을 추가해서 새로운 그래프 얻을 수 있다. 그러면 그래프 의 두 정점 사이의 최단 경로의 길이를 생각하고 이 길이들 중 최댓값에 주목한다. 이 최댓값을 그래프 의 지름(diameter)라고 부른다. 우리는 그래프 의 지름이 최소가 되도록 추가하는 간선을 찾고 싶다. 특별히 임의의 실수 에 대해서, 의 지름이 이하가 되는 추가 간선이 존재하는지 여부를 결정하는 문제에 대해 시간 알고리즘을 제안한다. 이것은 이전 알려진 시간복잡도 을 개선한다. 이 결정 알고리즘을 이용해서 주어진 경로 의 길이 에 대해서, 의 지름의 최솟값을 찾는 시간 알고리즘을 제안한다.

영어초록

This paper deals with the graph in which the weights of edges are given the distances between two end vertices on a metric space. In particular, we will study about a path with vertices for these graphs. We obtain a new graph by augmenting an edge to . Then the length of the shortest path between two vertices on is considered and we focus on the maximum of these lengths. This maximum is called the diameter of the graph . We wish to find the augmented edge to minimize the diameter of . Especially, for an arbitrary real number , we should determine whether the diameter of is less than or equal to and we propose an -time algorithm for this problem, which improves on the time complexity previously known. Using this decision algorithm, for the length of , we provide an -time algorithm to find the minimum of the diameter of .

참고자료

· 없음