随着因特网中应用的爆炸性增长与网络通讯技术的发展，无论在国防、财政和电源产业等传统领域，还是在新兴的可信计算和网络、云计算系统和下一代互联网等领域，网络的可靠性都得到越来越多的重视。如何在最小化占用网络资源的同时，通过网络的拓扑结构提高网络的可靠性，吸引了广大研究者的兴趣。在本文中，我们集中研究了这个课题中的两个基础问题：Min-Min 问题与Steiner 网络问题。　　 对于给定的带权图G=(V,E)以及源与目的结点s，t,Min-Min 问题要求计算两条不相交的-路径，使得其中较短的路径的权值最小。我们首先用一个反例指出了Bhatia等人关于无向图中边不相交Min-Min 问题的NP-完全性证明是不成立的；然后给出了该问题NP-完全性的一个正确证明。我们的证明基于一个从MAX-2SAT 问题的归约。在此之后，我们研究了平面图中的Min-Min 问题，并证明了Min-Min 问题在有向平面图中是NP-完全的。我们这些关于Min-Min问题的工作填补了目前理论上的一些空白。　　 对于给定的带权图G=(V,E)、终端集S(∈)V以及给定的正整数，k-点/边连通的Steiner 网络问题要求计算的一个子图，使得权值最小且终端间的点/边连通度不小于。我们首先总结了已有文献中Steiner网络问题的相关工作，然后分别设计了2,3-点连通的Steiner网络问题的近似比为2 与8的近似算法。　　 接着，我们扩展了我们的算法，从得到了一个增加k-1边连通的Steiner 网络连通度，使之成为k-边连通Steiner 网络的2-近似算法。最后我们用一个反例，指出我们的算法不能直接扩展到点连通的Steiner网络问题。