Sökning: onr:"swepub:oai:DiVA.org:kth-79034" >
Finding a simple pa...
Finding a simple path with multiple must-include nodes
-
- Vardhan, Hars (författare)
- The University of Texas at Dallas
-
- Billenahalli, Shreejith (författare)
- The University of Texas at Dallas
-
- Huang, Wanjun (författare)
- The University of Texas at Dallas
-
visa fler...
-
- Razo, Miguel (författare)
- The University of Texas at Dallas
-
- Sivasankaran, Arularasi (författare)
- The University of Texas at Dallas
-
- Tang, Limin (författare)
- The University of Texas at Dallas
-
- Monti, Paolo (författare)
- KTH,Fotonik,NEGONET
-
- Tacca, Marco (författare)
- The University of Texas at Dallas,OPNEAR Laboratory
-
- Fumagalli, Andrea (författare)
- The University of Texas at Dallas,OPNEAR Laboratory
-
visa färre...
-
(creator_code:org_t)
- 2009
- 2009
- Engelska.
-
Ingår i: 2009 IEEE INTERNATIONAL SYMPOSIUM ON MODELING, ANALYSIS & SIMULATION OF COMPUTER AND TELECOMMUNICATION SYSTEMS (MASCOTS). - 9781424449262 ; , s. 607-609
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- This paper presents an algorithm to find a simple path in the given network with multiple must-include nodes in the path. The problem of finding a path with must-include node(s) can be easily found in some special cases. However, in general, including multiple nodes in the simple path has been shown to be NP-Complete. This problem may arise in network areas such as forcing the route to go through particular nodes, which have wavelength converter (optical), have monitoring provision (telecom), have gateway functions (in OSPF) or are base stations (in MANET). In this paper, a heuristic algorithm is described that follows divide and conquer approach, by dividing the problem in two subproblems. It is shown that the algorithm does not grow exponentially in this application and initial re-ordering of the given sequence of must-include nodes can improve the result. The experimental results demonstrate that the algorithm successfully computes in reasonable time.
Ämnesord
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Telekommunikation (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Telecommunications (hsv//eng)
Nyckelord
- MANET;NP-complete;OSPF;base stations;divide-and-conquer approach;gateway functions;heuristic algorithm;multiple must-include nodes;near optimal path;optical wavelength converter;simple path finding;telecom monitoring provision;computational complexity;telecommunication network routing
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas