최소 라우팅 비용 스패닝 트리

Minimum routing cost spanning tree

컴퓨터 과학에서, 가중 그래프의 최소 라우팅 비용 스패닝 트리는 트리의 정점 사이의 쌍방향 거리의 합을 최소화하는 스패닝 트리이다.최적 거리 스패닝트리, 최단 총 경로 길이 스패닝트리, 최소 총 거리 스패닝트리 또는 최소 평균 거리 스패닝트리라고도 불립니다가중치 없는 그래프에서 이것은 최소 Wiener [1]인덱스의 스패닝 트리입니다.후(1974)는 이 나무들을 만드는 문제가 프란체스코 마피올리에 [2]의해 제안되었다고 쓰고 있다.

가중치가 부여되지 않은 [3][4]그래프에 대해서도 NP-난이도입니다.그러나 다항식 시간 근사 체계를 가지고 있다.근사치는 입력 그래프의 정점 수가 아닌 근사 비율에 따라 달라지는 kk)를 선택하고 k k의 [5]내부 를 가진 모든 트리를 검색하는 방식으로 작동합니다.

가중치 없는 간격 그래프의 최소 라우팅 비용 스패닝 트리는 선형 [6]시간으로 구성할 수 있습니다.다항식 시간 알고리즘은 거리 상속 그래프에도 알려져 있으며 가중 거리는 유전이 [7]된다.

레퍼런스

  1. ^ Dobrynin, Andrey A.; Entringer, Roger; Gutman, Ivan (2001). "Wiener index of trees: theory and applications". Acta Applicandae Mathematicae. 66 (3): 211–249. doi:10.1023/A:1010767517079. MR 1843259. S2CID 116000819.
  2. ^ Hu, T. C. (1974). "Optimum communication spanning trees". SIAM Journal on Computing. 3 (3): 188–195. doi:10.1137/0203015. MR 0427116.
  3. ^ Johnson, D. S.; Lenstra, J. K.; Rinnooy Kan, A. H. G. (1978). "The complexity of the network design problem" (PDF). Networks. 8 (4): 279–285. doi:10.1002/net.3230080402. MR 0514463.
  4. ^ Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.1: ND3, 페이지.206.
  5. ^ Wu, Bang Ye; Lancia, Giuseppe; Bafna, Vineet; Chao, Kun-Mao; Ravi, R.; Tang, Chuan Yi (2000). "A polynomial-time approximation scheme for minimum routing cost spanning trees" (PDF). SIAM Journal on Computing. 29 (3): 761–778. doi:10.1137/S009753979732253X. MR 1740574. S2CID 1639329.
  6. ^ Dahlhaus, Elias; Dankelmann, Peter; Ravi, R. (2004). "A linear-time algorithm to compute a MAD tree of an interval graph". Information Processing Letters. 89 (5): 255–259. doi:10.1016/j.ipl.2003.11.009. MR 2032568.
  7. ^ Dahlhaus, E.; Dankelmann, P.; Goddard, W.; Swart, H. C. (2003). "MAD trees and distance-hereditary graphs". Discrete Applied Mathematics. 131 (1): 151–167. CiteSeerX 10.1.1.86.6022. doi:10.1016/S0166-218X(02)00422-5. MR 2016490.
Stub icon

이 알고리즘 또는 데이터 구조 관련 문서는 stub입니다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.