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)
Copyright: © 2017 |Pages: 21
DOI: 10.4018/978-1-5225-2229-4.ch001

Abstract

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
Top

Introduction

Let 978-1-5225-2229-4.ch001.m01 be an undirected edge-weighted graph with vertex set 978-1-5225-2229-4.ch001.m02 and edge set 978-1-5225-2229-4.ch001.m03 such that 978-1-5225-2229-4.ch001.m04 and 978-1-5225-2229-4.ch001.m05. A spanning subgraph 978-1-5225-2229-4.ch001.m06 in 978-1-5225-2229-4.ch001.m07 is said to be a t-spanner subgraph if the distance between every pair of vertices in 978-1-5225-2229-4.ch001.m08 is at most 978-1-5225-2229-4.ch001.m09 times the shortest distance between the two vertices in 978-1-5225-2229-4.ch001.m10. The value of 978-1-5225-2229-4.ch001.m11, called the stretch factor, quantifies the quality of the distance approximation of the corresponding t-spanner subgraph. The goodness of t-spanner subgraph 978-1-5225-2229-4.ch001.m12 is estimated by either its total weight or the distance approximation of 978-1-5225-2229-4.ch001.m13 (stretch factor t of) (D. Peleg and J. D. Ulman, 1989).

We concern with the following two problem. The first problem, called the Minimum t-Spanner Subgraph (MtSS), we are given a value of stretch factor 978-1-5225-2229-4.ch001.m14 and the problem requires to find the t-spanner subgraph of the minimum total weight in 978-1-5225-2229-4.ch001.m15. The problem of finding a tree t-spanner with the smallest possible value of 978-1-5225-2229-4.ch001.m16 is known as the Minimum Maximum Stretch Spanning Tree (MMST) problem (Y. Emek and D. Peleg, 2008).

The t-spanner subgraph problem is widely applied in communication networks and distributed systems. For example, the MMST problem is applied to the arrow distributed directory protocol that supports the mobile object routing (M. J. Demmer & M. P. Herlihy, 1998). In particular, it is used to minimize the delay of mobile object routing from the source node to every client node in case of concurrent requests through a routing tree. The worst case overhead the ratio of the protocol is proportional to the maximum stretch factor of the tree (see (D. Peleg & E. Reshef, 2001)). Kuhn and Wattenhofer (2006) showed that the arrow protocol is a distributed ordering algorithm with low maximum stretch factor. Another application of the MMST is in the analysis of competitive concurrent distributed queuing protocols that intend to minimize the message transit in a routing tree (M. Herlihy, et al, 2001).

Complete Chapter List

Search this Book:
Reset