Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/10715Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Nomikos, C. | en |
| dc.contributor.author | Pagourtzis, A. | en |
| dc.contributor.author | Zachos, S. | en |
| dc.date.accessioned | 2015-11-24T17:00:09Z | - |
| dc.date.available | 2015-11-24T17:00:09Z | - |
| dc.identifier.issn | 0020-0190 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10715 | - |
| dc.rights | Default Licence | - |
| dc.subject | algorithms | en |
| dc.subject | all-optical networks | en |
| dc.subject | routing | en |
| dc.subject | path coloring | en |
| dc.subject | parallel fiber links | en |
| dc.subject | directed fiber trees | en |
| dc.subject | graphs | en |
| dc.title | Routing and path multicoloring | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2001 | - |
| heal.abstract | In optical networks it is important to make an optimal use of the available bandwidth. Given a set of requests the goal is to satisfy them by using a minimum number of wavelengths. We introduce a variation to this well known problem, by allowing multiple parallel links, in order to be able to satisfy any set of requests even if the available bandwidth is insufficient. In this new approach the goal is to use a minimum number of active links and thus reduce network pricing. In graph-theoretic terms, given a graph, a list of pairs of vertices, and a number of available colors, the goal is to route paths with the given pairs of vertices as endpoints and to find a color assignment to paths that minimizes color collisions over all possible routings and colorings. We present efficient algorithms for simple network topologies. For chains our solutions are optimal; for stars and rings - where it is NP-hard to solve the problem optimally - our solutions are approximate within a factor two of the optimal solution. The key technique involves transformation to edge coloring of bipartite graphs. For rings we also present a 2-approximation algorithm, for a variation of the problem, in which the routing is already prescribed. (C) 2001 Elsevier Science B.V. All rights reserved. | en |
| heal.journalName | Information Processing Letters | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| nomikos-2001-Routing and path multicoloring.pdf | 92.4 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
