Title page for etd-0825103-160926


[Back to Results | New Search]

URN etd-0825103-160926
Author Ming-You Chen
Author's Email Address chenmy@isl.cse.nsysu.edu.tw
Statistics This thesis had been viewed 5358 times. Download 2736 times.
Department Computer Science and Engineering
Year 2002
Semester 2
Degree Master
Type of Document
Language zh-TW.Big5 Chinese
Title Efficient Algorithms for Computing Shortest Path on Directed and Undirected Double-Loop Networks
Date of Defense 2003-07-11
Page Count 28
Keyword
  • Routing Algorithm
  • Shortest Path
  • Double Loop Networks
  • Abstract 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.
    Advisory Committee
  • Xuding Zhu - chair
  • Chun-Hung Richard Lin - co-chair
  • Chang-Biau Yang - co-chair
  • D. J. Guan - advisor
  • Files
  • etd-0825103-160926.pdf
  • indicate in-campus access immediately and off_campus access in a year
    Date of Submission 2003-08-25

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys