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

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).