Return to search

Efficient Algorithms for Computing Shortest Path on Directed and Undirected Double-Loop Networks

In this thesis, we present two e cent algorithms to compute shortest path
between pair of vertices in directed and undirected double-loop networks.
The algorithm for undirected double-loop networks is based on the concept
"packed basis" proposed by Janez Zerrovnik and Toma z Pisanski. With
O(logN) preprocessing time, both algorithms need only constant time to
compute the shortest path between any pair of vertices in the network. This
is an improvement of the best known algorithm, which needs O(l) time, where
l is the length of the path in the directed double-loop networks. These algo-
rithms are useful in message routing in the double-loop networks. Once the
network has been constructed, the parameters for computing the shortest
paths can be computed. At the time a message is to be delivered, the algo-
rithm needs only constant time to determine which edge the message should
be sent.

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0825103-160926
Date25 August 2003
CreatorsChen, Ming-You
ContributorsChun-Hung Richard Lin, D. J. Guan, Chang-Biau Yang, Xuding Zhu
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageCholon
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0825103-160926
Rightsoff_campus_withheld, Copyright information available at source archive

Page generated in 0.0023 seconds