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

You are using a new version of the IGI Global website.
If you experience a problem, submit a ticket to
helpdesk@igi-global.com,
and continue your work on the old website.

Acquire a Source of Open Access (OA) APC Funding for Your Institution Through IGI Global's OA Fee Waiver (Offset Model) Initiative

For any library that invests in IGI Global's InfoSci-Books and/or InfoSci-Journals databases, IGI Global will match the library’s investment with a fund of equal value to go toward subsidizing the OA APCs for their faculty patrons when their work is submitted/accepted under OA into an IGI Global journal.

Subscribe to the Latest Research Through IGI Global's InfoSci-OnDemand Plus

InfoSci®-OnDemand Plus, a subscription-based service, provides researchers the ability to access full-text content from over 100,000+ peer-reviewed book chapters and 25,000+ scholarly journal articles that spans across 350+ topics in 11 core subjects. Users can select articles or chapters that meet their interests and gain access to the full content permanently in their personal online InfoSci-OnDemand Plus library.

Purchase the Encyclopedia of Information Science and Technology, Fourth Edition

and Receive Complimentary E-Books of Previous Editions

When ordering directly through IGI Global's Online Bookstore, 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 an Additional 5% Discount on All Purchases

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

Receive a 20% Discount on All Publications Purchased Through IGI Global’s Online Bookstore

This discount cannot be combined with any other offer and is only valid when purchasing directly through IGI Global. (Exclusion of select titles and products may apply).

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. 18 Feb. 2020. 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 February 18, 2020. 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).