Constructing 2-connected graphs

OData support
Dr. Tapolcai János
Department of Telecommunications and Media Informatics

The topologies of communication networks are modeled with graphs. These graphs are connected, because the network nodes should be able to communicate with each other just in this case. Nevertheless, there can be some failure in the network, which can damage the continuous communication. These are the reasons why network topologies are designed multiple-connected. Sometimes the network topology changes, so we need construction sequences, which don’t damage the properties of the network.

After the introduction we overview the basic graph concepts in Chapter 1. These concepts help us to understand some other concepts and important theorems used later in this thesis. In Chapter 2 we show basic graph algorithms which help us in constructing more complex algorithms. Chapter 3 has two parts. First we show how to construct 2-connected graphs. We use the ear-decomposition algorithm. After these we present the differences between construction methods for 3-connected and 2-connected graphs.

In Chapter 4 we review a Hungarian C++ graph library called LEMON (Library for Efficient Modeling and Optimization in Networks), which help us to implement ear-decomposition algorithm. The source code of this algorithm is in Appendix. The last chapter of the thesis contains the assessment and some possible further developments.


Please sign in to download the files of this thesis.