트리 스패너

그래프 $G{\displaystyle }$ ${\displaystyle G}$의 트리 k-spanner(또는 단순히 k-spanner)는$$ $G{\displaystyle }$ ${\displaystyle G}$의 스패닝 하위 $트리{\displaystyle }$ T ${\displaystytle$ $T$$}$이며, 정점 쌍 사이의 거리는 $G{\displaystyle }$ ${\displaystyty G}$에서 최대 k$}$배이다$$$.$

알려진 결과

나무 스패너에 관한 논문이 몇 개 쓰여 있다.그 중 하나는 수학자 라이젠 카이(Leizhen Cai)와 데릭 코네일(Derek Corneil)이^[1] 쓴 트리 스패너(Tree Spanner)라는 제목으로, 트리 스패너와 관련된 이론적, 알고리즘적 문제를 탐구했다.그 논문의 결론 중 일부는 아래에 열거되어 있다.${\displaystyle n}$ ${\displaystyle n}$은(는) 항상 그래프의 정점 수이고$$, $m{\displaystyle }$ ${\displaystyle m}$은(는) 가장자리 수입니다.

1. A tree 1-spanner, if it exists, is a minimum spanning tree and can be found in ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$ time (in terms of complexity) for a weighted graph, where ${\displaystyle \beta (m,n)=\min \left\{i\mid \log ^{i}n\leq m/n\r$또한 $모든$ 나무$$1-스패너 허용 가중 그래프에는 고유한 최소 스패닝 트리가 포함되어 있다$.$
2. 트리 2-스팬너는 $($+ ${\displaystyle n}$) {\$displaystyle {\mathcal {O}(m+n)}$번으로 구성할 수$$ 있으며 트리 $t{\displaystyle }$ ${\displaystyt t$$}$ -spanner$$ 문제는 고정 t> ${\displaysty$t$>3}$에 대해 NP-완전이다
3. The complexity for finding a minimum tree spanner in a digraph is ${\displaystyle {\mathcal {O}}((m+n)\cdot \alpha (m+n,n))}$, where ${\displaystyle \alpha (m+n,n)}$ is a functional inverse of the Ackermann function
4. 가중 그래프의 최소 1-스팬은 $O{\displaystyle \mathcal{}(m}$ ${\displaystyle n}$+ n ${\displaystyle 2}$ ${\displaystyle \mathrm{로그}}$log ${\displaystyle (}$n $){\displaystyle {\mathcal{O}}(mn+n^{2$)에서 찾을 수 있다.$}\log(n)}$시간$$.
5. 고정된 합리적 숫자 > ${\displaystyle t>1}$의 경우 모든 에지 가중치가 양의 정수인 경우에도 가중 그래프에 트리 t-스패너가 포함되어 있는지 여부를 결정하는 것은 NP-완전이다.
6. digraph의 트리 스패너(또는 최소 트리 스패너)는 선형적으로 찾을 수 있다.
7. 디그래프에는 나무 스패너가 하나쯤 들어 있다.
8. 가중치 digraph의 준트리 스패너는 $O{\displaystyle \mathcal{}(m}$ ${\displaystyle \log \beta }$(${\displaystyle m}$, n$){\displaystyle {\mathcal{O}}(m\log \beta (m,n))}$번에서$$ 확인할 수 있다.

참고 항목

• 그래프스패너
• 기하 스패너

참조

• Handke, Dagmar; Kortsarz, Guy (2000), "Tree spanners for subgraphs and related tree covering problems", Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000 Konstanz, Germany, June 15–17, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1928, pp. 206–217, doi:10.1007/3-540-40064-8_20, ISBN 978-3-540-41183-3.