T-Spanner Problem: Genetic Algorithms for the T-Spanner Problem: Computer Science & IT Book Chapter | IGI Global

×

Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore.
Additionally, libraries can receive an extra 5% discount. Learn More

Encyclopedia of Information Science and Technology, Fourth Edition (10 Volumes) Now 50% Off

Take 50% off when purchasing the Encyclopedia directly through IGI Global's Online Bookstore. Plus, receive the complimentary e-books for the first, second, and third editions with the purchase of the Encyclopedia of Information Science and Technology, Fourth Edition e-book.

Create a Free IGI Global Library Account to Receive a 25% Discount on All Purchases

Exclusive benefits include one-click shopping, flexible payment options, free COUNTER 4 and MARC records, and a 25% discount on all titles as well as the award-winning InfoSci^{®}-Databases.

InfoSci^{®}-Journals Annual Subscription Price for New Customers: As Low As US$ 5,100

This collection of over 175 e-journals offers unlimited access to highly-cited, forward-thinking content in full-text PDF and XML with no DRM. There are no platform or maintenance fees and a guarantee of no more than 5% increase annually.

Moharam, Riham, Ehab Morsy and Ismail A. Ismail. "T-Spanner Problem: Genetic Algorithms for the T-Spanner Problem." Handbook of Research on Machine Learning Innovations and Trends. IGI Global, 2017. 1-21. Web. 23 Jul. 2018. doi:10.4018/978-1-5225-2229-4.ch001

APA

Moharam, R., Morsy, E., & Ismail, I. A. (2017). T-Spanner Problem: Genetic Algorithms for the T-Spanner Problem. In A. Hassanien, & T. Gaber (Eds.), Handbook of Research on Machine Learning Innovations and Trends (pp. 1-21). Hershey, PA: IGI Global. doi:10.4018/978-1-5225-2229-4.ch001

Chicago

Moharam, Riham, Ehab Morsy and Ismail A. Ismail. "T-Spanner Problem: Genetic Algorithms for the T-Spanner Problem." In Handbook of Research on Machine Learning Innovations and Trends, ed. Aboul Ella Hassanien and Tarek Gaber, 1-21 (2017), accessed July 23, 2018. doi:10.4018/978-1-5225-2229-4.ch001

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.

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