Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán nhanh cho cây Steiner
Tóm tắt
Cho một đồ thị khoảng cách vô hướng G=(V, E, d) và một tập S, trong đó V là tập hợp các đỉnh trong G, E là tập hợp các cạnh trong G, d là một hàm khoảng cách ánh xạ E vào tập hợp các số không âm và S⊑V là một tập con của các đỉnh V, bài toán cây Steiner là tìm một cây của G mà bao phủ S với tổng khoảng cách trên các cạnh là tối thiểu. Trong bài báo này, chúng tôi phân tích một thuật toán heuristic cho bài toán cây Steiner. Thuật toán heuristic này có độ phức tạp thời gian trường hợp xấu nhất là O(¦S¦¦V¦
2) trên một máy tính truy cập ngẫu nhiên và nó đảm bảo xuất ra một cây bao phủ S với tổng khoảng cách trên các cạnh không lớn hơn 2(1−1/l) lần tổng khoảng cách của cây tối ưu, trong đó l là số lá trong cây tối ưu.
Từ khóa
#cây Steiner #thuật toán heuristic #độ phức tạp thời gianTài liệu tham khảo
Gilbert, E.N., Pollak, H.O.: Steiner minimal tree. SIAM J. Appl. Math. 16, 1–29 (1968)
Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. Proc. of the 8th Annual ACM Symposium on Theory of Computing, pp. 10–22 1976
Dijkstra, E.N.: A note on two problems in connection with graphs. Numer. Math. 1, 269–271 (1959)
Floyd, R.W.: Algorithm 97: shortest path, CACM 5, 345 (1962)
Tabourier, Y.: All shortest distances in a graph: an improvement to Dantzig's inductive algorithm, Discrete Math. 4, 83–87 (1973)
Yao, A.C.C.: An O(¦E¦ loglog¦V¦) algorithm for finding minimal spanning tree. Information Processing Lett. 4, 21–23 (1975)
Cheriton, D., Tarjan, R.E.: Finding minimal spanning tree, SIAM J. Comput. 5, 724–742 (1976)
Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of computer computations (R.E. Miller, J.W. Thatcher eds.), pp. 85–104. New York: Plenum Press 1972
Hwang, F.K.: On Steiner minimal trees with rectilinear distance, SIAM J. Appl. Math. 30, 104–114 (1976)