Satisfying a maximum number of pre-routed requests in all-optical rings
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nomikos, C.
Pagourtzis, A.
Zachos, S.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Computer Networks-the International Journal of Computer and Telecommunications Networking
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
We address the problem of maximizing the number of satisfied requests in all-optical networks that use wavelength division multiplexing. We consider the case where requests are pre-routed and formulate it as the maximum path coloring problem. We study the problem for rings and present a (2/3)-approximation algorithm. Along the way we develop a fast matching technique for a special class of bipartite graphs. By using this technique we achieve an 0(n + m log L) time complexity for our approximation algorithm, where n is the number of nodes, m is the number of requests and L is the maximum load of requests on a single link. (C) 2002 Elsevier Science B.V. All rights reserved.
Περιγραφή
Λέξεις-κλειδιά
maximum path coloring, all-optical rings, wavelength assignment, approximation algorithms, directed fiber trees, networks, graphs, algorithms
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής