Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Finding a simple path with multiple must-include nodes
The University of Texas at Dallas.
The University of Texas at Dallas.
The University of Texas at Dallas.
The University of Texas at Dallas.
Show others and affiliations
2009 (English)In: 2009 IEEE INTERNATIONAL SYMPOSIUM ON MODELING, ANALYSIS & SIMULATION OF COMPUTER AND TELECOMMUNICATION SYSTEMS (MASCOTS) / [ed] Bradley, JT; Conrad, JM; Field, AJ; Harder, U; Knottenbelt, WJ; Riley, GF, 2009, 607-609 p.Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
2009. 607-609 p.
Keyword [en]
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;
National Category
Telecommunications
Identifiers
URN: urn:nbn:se:kth:diva-79034DOI: 10.1109/MASCOT.2009.5366808ISI: 000275140200066Scopus ID: 2-s2.0-76349101143ISBN: 978-142444926-2 (print)OAI: oai:DiVA.org:kth-79034DiVA: diva2:494700
Conference
17th IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems. Imperial Coll London, S Kensington Campus, London, ENGLAND. SEP 21-23, 2009
Note

QC 20150706

Available from: 2012-02-08 Created: 2012-02-08 Last updated: 2015-07-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Monti, Paolo

Search in DiVA

By author/editor
Monti, Paolo
By organisation
Photonics (Closed 20120101)
Telecommunications

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 478 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf