建造一個具有低成本且可信賴的網路時，網路的拓樸設計就是一個相當重要的理論。在這篇論文中，我們考慮低鏈結需求網路設計問題和存活網路設計問題。由於低鏈結需求網路設計問題包含了史坦那樹(Steiner tree)的理論，所以它是一個未定多項式難度(NP-Hard)的問題。我們利用divide-and-conquer的觀念去拆解低鏈結需求網路設計問題成為兩個部份；type 2的問題和type (0,1)的問題。首先，我們發展一個結合了深度優先搜尋演算法和cycle-shrinking的啟發式演算法去解type 2的問題。接著，我們利用Mehlhorn的演算法求解type (0,1)的問題。最後，我們結合上述兩步驟的結果再加以改進，求得一組符合低鏈結需求網路設計問題的網路拓樸。藉由Mehlhorn的演算法，我們可以估計我們所提出的啟發式演算法所求得的解與最佳解間大約的界限。在歐基里德網路的例子中，這個界限界於2.47到2.81之間。在非歐基里德網路的例子中，這個界限界於3.08到13.76之間。根據實驗的結果，我們提出的演算法在處理符合歐基里德(Euclidean)網路的例子時，可以比在處理非歐基里德(Non-Euclidean)網路的例子時有更好的結果與較短的計算時間。我們也發現在處理不同問題大小的例子時，我們所提出演算法的表現並不會有很明顯地影響。

Network design problem is an important issue to build an economical and reliable system. In this thesis, we consider the low-connectivity network design (LCND) problem and survivable network design (SND) problem. The LCND is NP-hard since it is the generalization of the Steiner tree problem. We use the divide-and-conquer idea to decompose the original LCND problem into two parts: type 2 problem and type (0,1) problem. We sequentially solve type 2 problem and type (0,1) problem. Firstly, we develop a heuristic algorithm combining depth-first search (DFS) and cycle-shrinking method to solve type 2 problem. Then, we use the Mehlhorn’s algorithm to solve type (0,1) problem. Finally, we use the final improvement procedure to get our LCND solution. By using Mehlhorn’s algorithm, we can evaluate the approximated bound of our LCND algorithm. For Euclidean instances, the approximated bounds are between 2.47 to 2.81. For Non-Euclidean instances, the approximated bounds are between 3.08 to 13.76. Base on the computational results, our LCND algorithm works better for Euclidean instance, with better bound and shorter time. We also find that there is no obvious relationship between the network size and the performance bound of our LCND algorithm.

[1] A. Balakrishnan, T.L. Magnanti, and P. Mirchandani. Connectivity-splitting models for survivable network design. Networks, 43(1):10–27, 2004.
[2] F. Barahona and L. Lad´anyi. Branch and cut based on the volume algorithm: Steiner trees in graphs and max-cut. RAIRO - Operations Research, 40:53–73, 2006.
[3] J.E. Beasley. An SST-based algorithm for the Steiner problem in graphs. Networks, 19:1–16, 1989.
[4] P. Berman and V. Ramaiyer. Improved approximations for the Steiner tree problem. Journal of Algorithms, 17:381–408, 1994.
[5] A. Candia-V´ejar and H. Bravo-Azl´an. Worst-case performance of Wong’s Steiner tree heuristic. Discrete Applied Mathematics, 154:730–737, 2006.
[6] F. Ducatelle and L. M. Gambardella. Survivable routing in IP-over-WDM networks: An efficient and scalable local search algorithm. Optical Switching and Networking, 2:86–99, 2005.
[7] A. Dutta and P. Kubat. Design of partially survivable networks for cellular telecommunication systems. European Journal of Operational Research, 118:52–64, 1999.
[8] K. P. Eswaran. Augmentation problems. SIAM J. Comput, 5:653–665, 1976.
[9] B. Fortz and M. Labb´e. Handbooks of optimization in telecommunications, chapter Design of survivable networks, pages 367–389. Springer, New York, 2006.
[10] A. Galluccio and G. Proietti. Polynomial time algorithms for 2-edge-connectivity augmentation problems. Algorithmica, 36:361–374, 2003.
[11] N. Garg, V. Santosh, and A. Singla. Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 103–111, 1993.
[12] M. Gendreau, J.F. Larochelle, and B. Sans´o. A tabu search heuristic for the Steiner tree problem. Networks, 34(2):162–172, 1999.
[13] M. Gr¨otschel, C. L. Monma, and M. Stoer. Handbooks in operations research and management science, volume 7, chapter Design of survivable networks, pages 617–672. Elsevier, Amsterdam, 1995.
[14] S. Hougardy and S. Kirchner. Lower bounds for the relative greedy algorithm for approximating Steiner trees. Networks, 47(2):111–115, 2006.
[15] S. Hougardy and H.J. Pr¨omel. A 1.598 approximation algorithm for the Steiner problem in graphs. In Proceedings of the tenth annual ACM-SIAM Symposium on Discrete algorithms, pages 448–453, 1999.
[16] T. S. Hsu and V. Ramachandran. A linear-time algorithm for triconnectivity augmentation.
In Proceedings of the 32rd Annu. Symp. on the Foundations of Computer Science,
pages 548–599, 1991.
[17] M. Karpinski and A. Zelikovsky. New approximation algorithms for the Steiner tree problems. Journal of Combinatorial Optimization, 1:47–65, 1997.
[18] H. Kerivin and A.R. Mahjoub. Design of survivable network: A survey. Networks, 46(1):1–21, 2005.
[19] H. Kerivin, D. Nace, and Thi-Tuyet-Loan Pham. Design of capacitated survivable networks with a single facility. IEEE/ACM TRANSACTIONS ON NETWORKING, 13:248–261, 2005.
[20] C. W. Ko and C. L. Monma. Heuristic methods for designing highly survivable communication networks. Technical report, Bell Communications Research, 1989.
[21] T. Koch and A. Martin. Solving Steiner tree problems in graphs to optimality. Networks, 32(3):207–232, 1998.
[22] P. Krysta. Approximating minimum size {1,2}-connected networks. Discrete Applied Mathematics, 125:267–288, 2003.
[23] A. Lucena and J.E. Beasley. A branch and cut algorithm for the Steiner problem in graphs. Networks, 31(1):39–59, 1998.
[24] T.L. Magnanti and S. Raghavan. Strong formulations for network design problems with connectivity requirements. Networks, 45(2):61–79, 2005.
[25] Kurt Mehlhorn. A faster approximation algorithm for the steiner problem in graphs. Information Processing Letters, 27:125–128, 1988.
[26] S. Menon and A. Amiri. Designing partially survivable cellular telecommunications networks. Information Technology and Management, 6:293–303, 2005.
[27] C. L. Monma and D. F. Shallcross. Methods for designing communication networks with certain two-connected survivability constraints. Operations Research, 37:531–541, 1989.
[28] Nash-Williams. On orientations, connectivity, and odd vertex pairings in finite graphs. Canadian J. Math, 12:555–567, 1960.
[29] T. Polzin and S.V. Daneshmand. Improved algorithms for the Steiner problem in networks. Discrete Applied Mathematics, 112:263–300, 2006.
[30] H.J. Pr¨omel and A. Steger. RNC-approximation algorithms for the Steiner problems. In Proceedings fourteenth Annual Symposium on Theoretical Aspects of Computer Science, pages 559–570, 1997.
[31] S. Raghavan. Low-connectivity network design on series-parallel graphs. NETWORKS, 43(3):163–176, 2004.
[32] G. Robins and A. Zelikovsky. Improved Steiner tree approximation in graphs. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pages 770–779, 2000.
[33] G. Robins and A. Zelikovsky. Tighter bounds for graph Steiner tree approximation. DSIAM Journal on Discrete Mathematics, 19:122–134, 2005.
[34] M. Saltouros, M. Theologou, M. Angelopoulos, and C.S. Ricudis. An efficient evolutionary algorithm for (Near-) optimal Steiner trees calculation: An approach to routing of multipoint connections. In Proceedings of the 3rd International Conference on Computational Intelligence and Multimedia Applications, pages 448–453, 1999.
[35] H. Takahahsi and A. Matsuyama. An approximate solution for the Steiner problem in graphs. Math. Jap, 24:573–577, 1980.
[36] Gue woong Jeong, Kyungsik Lee, Sungsoo Park, and Kyungchul Park. A branch-andprice algorithm for the Steiner tree packing problem. Computers & Operations Research, 29:221–241, 2002.
[37] A. Zelikovsky. An 11/6-approximation algorithm for the network Steiner problem. Algorithmica, 9:463–470, 1993.
[38] A. Zelikovsky. Better approximation bounds for the network and Euclidean Steiner tree problems. Technical Report CS-96-06, University of Virginia, 1996.
[39] L. Zhao, H. Nagamochib, and T. Ibaraki. A primal-dual approximation algorithm for the survivable network design problem in hypergraphs. Discrete Applied Mathematics, 126:275–289, 2003.