A geometric network is a weighted undirected graph $\sl{G}$ whose vertices are points in $\mathbb{R}^d$, and weights are the Euclidean length of its edges. The graph distance between the two vertices in a geometric network is the length of shortest path connecting those points. The dilation of $\sl{G}$ is the maximum factor by which graph distance differs from the Euclidean distance between two points. The anchored dilation of $\sl{G}$ is the dilation from an anchor, a fixed given point, to other vertices. We consider the Anchored Dilation Bounded Minimum Spanning Tree(ADBMST) Problem. The problem is to build the spanning tree which has the minimum weight among all spanning trees with the anchored dilation at most $\delta$ for a given set of $\sl{n}$ points S and maximum dilation $\delta > 1$. I show that the problem is NP-hard by showing that there is a polynomial reduction from the Knapsack Problem to ADBMST Problem. I also suggest a simple algorithm to build an approximated tree.
기하 네트워크를 구성하는 문제는 무선센서네트워크에서 활용될 수 있는데, 멀티캐스팅이나 데이터중심적 라우팅을 하기 위하여 라우터는 신장트리를 구성한다. 이 때 라우팅의 효율성과 시간 지연이 중요한 요소인데, 둘 사이에는 서로 반대급부가 있다. 우리는 루트에서의 거리에 따른 상대적인 시간지연을 고려하여 Anchored Dilation이라는 개념을 도입하고, 이것은 G=(V,E)가 주어졌을 때, 주어진 한 점 $r \in V$ 으로 부터 다른 한 점 $v \in S$ 까지의 유클리안 거리(Euclidean distance)와 그래프 거리(E의 간선들만을 이용하여 간 거리)의 비율이 가장 큰 값을 말한다. 우리는 네트워의 중요한 요소를 고려하여, 최대 Anchored Dilation을 일정한 값 이하로 $\delta$로 제한하면서 최소 비용 신장 트리를 찾는 문제를 제안한다. 제한된 값이 아주 크다면, 최소 비용 신장 트리를 찾는 문제와 같게 되지만, 그렇지 않다면 최소 비용과 Anchored Dilation 사이에 상호 반대급부적 관계가 발생하고, 이것에 착안해서, NP-Complete로 잘 알려진 배낭 문제(Knapsack Problem)를 이 문제로 다항시간 내에 Reduction함으로써, 이 문제가 NP-hard임을 보인다. Reduction 방법으로 평면에 점들을 특별하게 배치하고, 이 점들로 이루어진 기하네트워크에서는 Anchored Dilation이 제한된 최소 신장트리가 각각의 물건에 해당하는 점들의 셋에서 2가지 형태만 가능한것을 보이고, 이것이 배낭문제에서 물건이 선택하거나, 선택하지 않을 때의 경우에 해당하게 하여, 두 해답이 일치함을 보인다. 그리고 기존의 t-spanner 알고리즘과 Dijkstra 알고리즘을 사용하여, 간단한 근사 알고리즘을 제시한다. 이 때, 근사알고리즘의 상수는 주어진 $\delta$에 의존하고, $\delta$에 의존하지 않는 알고리즘은 앞으로의 과제이다.
