ΛΗΚΥΘΟΣ
    • English
    • Ελληνικά
  • English 
    • English
    • Ελληνικά
  • Login
View Item 
  •   LEKYTHOS Home
  • Κυπριακή ερευνητική παραγωγή / Cyprus research production
  • Αρχείο Μεταπτυχιακών διατριβών
  • Πανεπιστήμιο Κύπρου
  • Τμήμα Πληροφορικής
  • View Item
  •   LEKYTHOS Home
  • Κυπριακή ερευνητική παραγωγή / Cyprus research production
  • Αρχείο Μεταπτυχιακών διατριβών
  • Πανεπιστήμιο Κύπρου
  • Τμήμα Πληροφορικής
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Evaluating the network survivability issue of k-best paths through graph theoretic techniques

Thumbnail
View/Open
Μεταπτυχιακή εργασία (581.9Kb)
Date
2005-06
Author
Στυλιανού, Μαρίνος
Stylianou, Marinos
Metadata
Show full item record
Abstract
In this thesis graph theoretic techniques are adopted for addressing the network survivability issue of disjoint paths selection. The evaluation was conducted after the implementation of a solver that produces a solution of the problem after successive application of two algorithms on any given topology, the algorithm of Louca et al [19] and Castanon’s [8]. The first algorithm transforms any networks into a trellis graph and the second exploits the special structure of the trellis graph and solves for the k-best paths using the minimum cost network flow (MCNF) algorithm. The transformation and evaluation of the K-best paths solution is illustrated for a number of topologies through the graphical user interface adapted from [37]. It is also contrasted with the k-successive approximation methods, which cannot guarantee the selection of the K-best paths, due to the successive removal of shortest paths at each iteration. Furthermore, the performance of the algorithm and its time complexity are investigated and also compared with Surballe’s Disjoint Pair Algorithm [31]. Even though the trellis transformations algorithm can find all possible disjoint paths in the vast majority of cases, pathological situations where the algorithm may fail is also identified in the thesis, analysed, and a solution is provided and evaluated.
URI
http://hdl.handle.net/10797/13103
Collections
  • Τμήμα Πληροφορικής [73]

DSpace software copyright © 2002-2015  DuraSpace
Contact Us | Send Feedback
 

 

Browse

All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

DSpace software copyright © 2002-2015  DuraSpace
Contact Us | Send Feedback