選擇內部節點最小生成樹問題之啟發式演算法

論文內容
論文分類	碩士論文
學號	g982109
姓名	劉展碩
標題	選擇內部節點最小生成樹問題之啟發式演算法
指導教授	陳彥宏
畢業日期	2011-10
附件檔案
參考連結	http://163.21.239.2/cgi-bin/cdrfb3/tmtcgsweb.cgi?o=dtmtccdr
摘要	本研究探討一個組合最佳化的問題：選擇內部節點最小生成樹問題（selected-internal minimum spanning tree problem）。給定一個無向完全圖G=(V,E)，一個非負數的權重函數（cost function）在邊上，一個內部節點的集合R包含於G與R’包含於R，選擇內部節點最小生成樹問題定義為：找出一個邊上權重加總最小的生成樹，連通V內的所有節點，但是R內的節點不能是樹葉（\|R\|>=2）。此問題可應用於群播繞徑、超大型積體電路繞線及演化樹重建。這個問題被證明為NP-Com
參考文獻	1. Biggs, N.L., Loyd, E.K., Wilson, R.J., Graph Theory. Clarendon Press, Oxford (1976) 2. Bjorklund, A., Husfeldt, T., Kaski, P.,Koivisto, M., The travelling salesman problem in bounded degree graphs. In Proceedings of the 35th international colloquium on Automata, Languages and Programming (ICALP 2008), Lecture Notes in Computer Science, Springer-Verlag 5125, 198-209 (2008) 3. Byrka, J., Grandoni, F., Rothvos, T., Sanita, L., An improved LP-based approximation for Steiner tree. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), 583-592 (2010) 4. Caldwell, A., Kahng, A., Mantik, S., Markov, I., Zelikovsky, A., On wirelength estimations for row-based placement. In Proceedings of the 1998 International Symposium on Physical Design, 4-11, (1998) 5. Catanzaro, D., The minimum evolution problem: overview and classification. Networks 53, 112–125 (2009) 6. Charikar, M., Naor, J., Schieber, B., Resource optimization in QoS multicast routing of real-time multimedia. IEEE/ACM Transactions Networking 12, 340–348 (2004) 7. Chen, Y.H., Lu, C.L., Tang, C.Y., On the full and bottleneck full Steiner tree problems. In: The Ninth International Computing and Combinatorics Conference (COCOON 2003), Lecture Notes in Computer Science, Springer-Verlag 2697, 122–129 (2003) 8. Cheng, X., Du, D.Z., Steiner Tree in Industry. Kluwer Academic Publishers, Dordrecht, Netherlands (2001) 9. Christofides, N., Worst-case analysis of a new heuristic for the traveling salesman problem. Carnegie-Mellon University Management Sciences Research Report 388, Pittsburgh, Pa. (1976) 10. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to Algorithm. 2nd edition, MIT Press, Cambridge (2001) 11. Dorigo, M., Gambardella, L.M., Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions On Evolutionary Computation 1, 53-66 (1997) 12. Drake, D.E., Hougardy, S., On approximation algorithms for the terminal Steiner tree problem. Information Processing Letters 89, 15-18 (2004) 13. Du, D.Z., Hu, X., Steiner Tree Problems in Computer Communication Networks. World Scientific Publishing Company (2008) 14. Du, D.Z., Smith, J.M., Rubinstein, J.H., Advances in Steiner tree. Kluwer Academic Publishers, Dordrecht, Netherlands (2000) 15. Dumitrescu, I., Ropke, S., Cordeau, J.F., Laporte, G., The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm. Mathematical Programming 121, 269-305 (2010) 16. Garey, M.R., Graham, R.L., Johnson, D.S., The complexity of computing Steiner minimal trees. SIAM Journal of Applied Mathematics 32, 835-859 (1997) 17. Hazewinkel, M., Encyclopaedia of Mathematics. Springer, (2001) 18. Hsieh, S.Y., Gao, H.M., On the partial-terminal Steiner tree problem. The Journal of Supercomputing 41, 41-52 (2007) 19. Hsieh, S.Y., Pi, W.H., On the partial-terminal Steiner tree problem. In: 9th International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN 2008), 173-177 (2008) 20. Hsieh, S.Y., Yang, S.C., Approximating the selected-internal Steiner tree. Theoretical Computer Science 381, 288-291 (2007) 21. Hwang, F.K., Richards, D.S., Winter, P., The Steiner Tree Problem. Annuals of Discrete Mathematics 53, Elsevier Science Publishers, Amsterdam, (1992) 22. Jozefowiez, N., Glover, F., Laguna, M., Multi-objective meta-heuristics for the traveling salesman problem with profits. Journal of Mathematical Modelling and Algorithms 7, 177-195 (2008) 23. Kahng, A.B., Robins, G.,On Optimal Interconnections for VLSI. Kluwer Publishers, (1995) 24. Kapsalis, A., Rayward-Smith, V.J., Smith, G.D., Solving the graphical Steiner tree problem using genetic algorithms. The Journal of the Operational Research Society 44, 397-406 (1993) 25. Korte, B., Promel, H.J., Steger, A., Steiner trees in VLSI-layout. In: Korte, B., Lovasz, L., Prommel, H.J., Schrijver, A. (eds.), Paths, Flow, and VLSI-layout, Springer-Verlag, 185-214 (1990) 26. Li, X., Zou, F., Huang, Y., Kim, D. Wu, W., A better constant-factor approximation for selected-internal Steiner minimum tree. Algorithmica 56, 333-341 (2010) 27. Lin, G.H., Xue, G.L, On the terminal Steiner tree problem. Information Processing Letters 84, 103-107(2002) 28. Lin, S., Kernighan, B.W., An effective heuristic algorithm for traveling salesman problem. Operations Research 21,498-516 (1973) 29. Lu, C.L., Tang, C.Y., Lee, R.C.T. , The full Steiner tree problem. Theoretical Computer Science 306, 55-67(2003) 30. Martineza, F.V., Pinab, J.C.D., Soares, J., Algorithm for terminal Steiner trees. Theoretical Computer Science 389, 133–142 (2007) 31. Oliver, W.L., Thomas, O’C., Flip, P., The traveling salesman problem in the natural environment. Nature Precedings (2010) 32. Robins, G., Zelikovsky, A., Tighter bounds for graph Steiner tree approximation. SIAM Journal on Discrete Mathematics 19, 122-134 (2005) 33. Robinson, J., On the Hamiltonian game (a traveling salesman problem). Rand Corporation (1949) 34. Snyder, L.V., Daskin, M.S., A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research 174, 38-53 (2006) 35. Xie, X.F., Liu, J., Multiagent optimization system for solving the traveling salesman problem (TSP). IEEE Transactions On Systems, Man, And Cybernetics Society 39, 489-502 (2009)

瀏覽數: