T-Spanner Problem: Genetic Algorithms for the T-Spanner Problem

T-Spanner Problem: Genetic Algorithms for the T-Spanner Problem

Riham Moharam (Suez Canal University, Egypt), Ehab Morsy (Suez Canal University, Egypt) and Ismail A. Ismail (6 October University, Egypt)
DOI: 10.4018/978-1-7998-8048-6.ch019
OnDemand PDF Download:
No Current Special Offers


The t-spanner problem is a popular combinatorial optimization problem and has different applications in communication networks and distributed systems. This chapter considers the problem of constructing a t-spanner subgraph H in a given undirected edge-weighted graph G in the sense that the distance between every pair of vertices in H is at most t times the shortest distance between the two vertices in G. The value of t, called the stretch factor, quantifies the quality of the distance approximation of the corresponding t-spanner subgraph. This chapter studies two variations of the problem, the Minimum t-Spanner Subgraph (MtSS) and the Minimum Maximum Stretch Spanning Tree(MMST). Given a value for the stretch factor t, the MtSS problem asks to find the t-spanner subgraph of the minimum total weight in G. The MMST problem looks for a tree T in G that minimizes the maximum distance between all pairs of vertices in V (i.e., minimizing the stretch factor of the constructed tree). It is easy to conclude from the literatures that the above problems are NP-hard. This chapter presents genetic algorithms that returns a high quality solution for those two problems.
Chapter Preview


In this section, we present results on related problems.

Complete Chapter List

Search this Book: