Computing the shortest network under a fixed topology
Tóm tắt
We show that, in any given uniform orientation metric plane, the shortest network interconnecting a given set of points under a fixed topology can be computed by solving a linear programming problem whose size is bounded by a polynomial in the number of terminals and the number of legal orientations. When the given topology is restricted to a Steiner topology, our result implies that the Steiner minimum tree under a given Steiner topology can be computed in polynomial time in any given uniform orientation metric with /spl lambda/ legal orientations for any fixed integer /spl lambda/ /spl ges/ 2. This settles an open problem posed by Brazil, Thomas and Weng (2000).
Từ khóa
#Computer networks #Network topology #Telecommunication network topology #Steiner trees #Costs #Circuit topology #Tree graphs #Linear programming #Polynomials #LawTài liệu tham khảo
10.1287/opre.41.6.1164
10.1007/BF02591963
10.1002/1097-0037(200007)35:4<287::AID-NET8>3.3.CO;2-I
10.1109/ISCAS.1995.523734
lee, 1996, The Steiner Minimal Tree Problem in the Plane, Proc Seventh Int'l Symp Algorithms and Computations, 247
10.1007/BF02579150
10.1007/978-1-4757-2363-2
10.1007/978-1-4757-3171-2_4
10.1137/0216049
10.1016/0167-6377(95)00050-X
10.1109/43.159995
10.1137/0132072
10.1137/0116001
10.1137/0114025
xue, 2000, Computing the Shortest Network with Routing under a Tree Topology with Applications, Proc 17th Int'l Symp Math Programming
10.1137/S0097539798347190
10.1006/jcss.1997.1513
10.1109/43.673630
10.1137/S1052623495288362
10.1007/BF01758755
hwang, 1992, The Steiner Tree Problems
10.1137/S1052623497327088
10.1137/0221059
10.1016/0196-6774(92)90050-M
10.1137/0806006
10.1137/S1064827598343954