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
OnDemand PDF Download:
$30.00
List Price: $37.50

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 be an undirected edge-weighted graph with vertex set and edge set such that and . A spanning subgraph in is said to be a t-spanner subgraph if the distance between every pair of vertices in is at most times the shortest distance between the two vertices in . The value of , called the stretch factor, quantifies the quality of the distance approximation of the corresponding t-spanner subgraph. The goodness of t-spanner subgraph is estimated by either its total weight or the distance approximation of (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 and the problem requires to find the t-spanner subgraph of the minimum total weight in . The problem of finding a tree t-spanner with the smallest possible value of 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