Shortest Euclidean Distance - Connected Steiner Networks

Let P be a finite set of points. A network N = (V, E) is called a Steiner network on P if P V, and particularly a spanning network on P if P = V. For a Steiner network N on P, points in P are called regular points, while points in V \ P are called Steiner points. The length of a network is defined to be the total length of all its edges. Given a finite set P of points in the Euclidean plane, the Euclidean 2-connected Steiner network problem is to find the shortest 2-connected Steiner network on P, where the length of an edge pq is definied as the Euclidean distance between the points p and q, and some extra points not in P may need. This problem has important applications in the design of economical and reliable communication networks.Luebke and Provan proved that the Euclidean 2-connected Steiner network problem is NP-hard, which means that there are few possibilities of existing a polynomial time algorithm for a general finite set P of points in the Euclidean plane. In 1998, Hsu and Hu introduced the concept of basic 2-connected Steiner networks, and gave some structural properties of (basic) shortest 2-connected Steiner networks and two polynomially-solvable cases. Li Meili, in her thesis, showed several structural properties of (basic) shortest 2-connected Steiner networks by using block graphs as tools and gave a clear proof of a result of Hsu and Hu. In this thesis, we give a further research on the Euclidean 2-connected Steiner network problem.In Chapter 1, after an introduction on terminology and notations, we give a survey on the Euclidean 2-connected Steiner network problem and a general introduction of the main results of the thesis.In Chapter 2, with a property of 2-connected networks given by Monma et al., we give several new structural properties of (basic) shortest 2-connected steiner (or spanning) networks, and more simple and clear proofs of three properties of (basic) shortest 2-connected Steiner networks presented by Li Meili.In Chapter 3, we mainly discuss the relationship among the shortest 2-connected Steiner network on P, the shortest 2-connected spanning network on P and its shortest Hamilton cycle when |P| = 6 or 7.2-connected Steiner network problem in metric space. In Chapter 4, we generalize several results on shortest 2-connected Steiner networks to general metric space.At the end of this thesis, we give a description of the generalized Euclidean Steiner problem and propose some problems for further research.