A genetic algorithm for finding the k shortest paths in a network
Most of the multimedia applications require the k shortest paths during the communication between a single source and multiple destinations. This problem is known as multimedia multicast routing and has been proved to be NP-complete. The paper proposes a genetic algorithm to determine the k shortest...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2010-12-01
|
| Series: | Egyptian Informatics Journal |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S111086651000023X |
| _version_ | 1818577089916305408 |
|---|---|
| author | Ahmed Younes Hamed |
| author_facet | Ahmed Younes Hamed |
| author_sort | Ahmed Younes Hamed |
| collection | DOAJ |
| description | Most of the multimedia applications require the k shortest paths during the communication between a single source and multiple destinations. This problem is known as multimedia multicast routing and has been proved to be NP-complete. The paper proposes a genetic algorithm to determine the k shortest paths with bandwidth constraints from a single source node to multiple destinations nodes. The algorithm uses the connection matrix of a given network, and the bandwidth of the links to obtain the k shortest paths. Some examples are provided to illustrate the effectiveness of this algorithm over conventional algorithms. |
| first_indexed | 2024-12-16T06:24:23Z |
| format | Article |
| id | doaj.art-4eb5032422424901a862b389f56a3f36 |
| institution | Directory Open Access Journal |
| issn | 1110-8665 |
| language | English |
| last_indexed | 2024-12-16T06:24:23Z |
| publishDate | 2010-12-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Egyptian Informatics Journal |
| spelling | doaj.art-4eb5032422424901a862b389f56a3f362022-12-21T22:41:03ZengElsevierEgyptian Informatics Journal1110-86652010-12-01112757910.1016/j.eij.2010.10.004A genetic algorithm for finding the k shortest paths in a networkAhmed Younes HamedMost of the multimedia applications require the k shortest paths during the communication between a single source and multiple destinations. This problem is known as multimedia multicast routing and has been proved to be NP-complete. The paper proposes a genetic algorithm to determine the k shortest paths with bandwidth constraints from a single source node to multiple destinations nodes. The algorithm uses the connection matrix of a given network, and the bandwidth of the links to obtain the k shortest paths. Some examples are provided to illustrate the effectiveness of this algorithm over conventional algorithms.http://www.sciencedirect.com/science/article/pii/S111086651000023XComputer networksShortest pathsGenetic algorithmsMultimedia |
| spellingShingle | Ahmed Younes Hamed A genetic algorithm for finding the k shortest paths in a network Egyptian Informatics Journal Computer networks Shortest paths Genetic algorithms Multimedia |
| title | A genetic algorithm for finding the k shortest paths in a network |
| title_full | A genetic algorithm for finding the k shortest paths in a network |
| title_fullStr | A genetic algorithm for finding the k shortest paths in a network |
| title_full_unstemmed | A genetic algorithm for finding the k shortest paths in a network |
| title_short | A genetic algorithm for finding the k shortest paths in a network |
| title_sort | genetic algorithm for finding the k shortest paths in a network |
| topic | Computer networks Shortest paths Genetic algorithms Multimedia |
| url | http://www.sciencedirect.com/science/article/pii/S111086651000023X |
| work_keys_str_mv | AT ahmedyouneshamed ageneticalgorithmforfindingthekshortestpathsinanetwork AT ahmedyouneshamed geneticalgorithmforfindingthekshortestpathsinanetwork |