Loading...
Please wait, while we are loading the content...
Similar Documents
A Genetic Approach for Solving Minimum Routing Cost Spanning Tree Problem
| Content Provider | Semantic Scholar |
|---|---|
| Author | Dadashi, Sahar Zadeh Gupta, Prashant K. Hegadi, Ravindra |
| Copyright Year | 2012 |
| Abstract | is one of spanning tree optimization problems having several applications in network design. In general case, the problem is proved to be NP-hard. The paper uses genetic (GA) approach to solve MRCT problem. Computational experiment results show that GA approach outperforms current approximation algorithms. In this section, we are going to represent some main terms related to MRCT problem, traditional approachs and their drawbacks. Given G = (V,E,w) is an undirected connected graph having non-negative edge weights (costs); in which V is the node set, E is the edge set, w is the cost matrix. Suppose T is a spanning tree in G, the routing cost of T, denoted by C(T), is the total routing costs of all vertex pairs in T, in which the routing cost of a vertex pair (u,v) in T, denoted by d T (u,v), is the sum over edge costs on the path connecting vertex u and vertex v in T. So, by definitions, we have: ∑ ∈ = V v u T v u d T C ,) , () ((1) The problem requirement is to to find the one having minimum routing cost among all possible spanning trees in G. Computing spanning tree routing cost of the one having n nodes in MRCT problems by definition occupies O(n 2) time. However, by the definition of " routing load " below we could compute spanning tree routing cost within linear time. Given a spanning tree T having edge set E(T). If remove an edge e from T, T is then separated into 2-subtrees of T 1 and T 2 having the node set of V(T 1) và V(T 2) respectively. Routing load of e is defined as follows: l(T,e) = 2⏐V(T 1)⎪.⏐V(T 2)⎪. The formula (1) is then equivalent to formula (2) as follows: ∑ ∈ =) () (). , () (T E e e w e T l T C (2) The MRCT problem is proved to be of NP-hard class. Edge weights and spanning tree topology are two factors affecting on spanning tree routing cost. The spanning tree topology affects highly on the graphs in which the bias of edge weights is not too high. Constructing a minimum routing cost spanning tree is equivalent to constructing a spanning tree so that the average length of vertex pairs is at least. The problem plays important role in applications of network system building. Specifically, … |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://ijmlc.org/papers/vol2no4-Contents.pdf |
| Alternate Webpage(s) | http://www.ijmlc.org/papers/155-C00896-009.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
