Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/26680Full 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-12-11T13:41:05Z | - |
| dc.date.available | 2015-12-11T13:41:05Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/26680 | - |
| dc.rights | Default License | - |
| dc.subject | - | en |
| dc.title | Randomized and approximation algorithms for blue-red matching | en |
| heal.type | bookChapter | - |
| heal.type.en | Book chapter | en |
| heal.type.el | Κεφάλαιο βιβλίου | el |
| heal.generalDescription | 715-725 σ. | el |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.publicationDate | 2007 | - |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 724-725 | el |
| heal.abstract | We introduce the Blue-Red Matching problem: given a graph with red and blue edges, and a bound w, find a maximum matching consisting of at most w edges of each color. We show that BLUE-Red Matching is at least as hard as the problem Exact MATCHING (Pa- padimitriou and Yannakakis, 1982), for which it is still open whether it can be solved in polynomial time. We present an RNC algorithm for this problem as well as two fast approximation algorithms. We finally show the applicability of our results to the problem of routing and assigning wavelengths to a maximum number of requests in all-optical rings. | en |
| heal.publisher | Springer Berlin / Heidelberg | en |
| heal.fullTextAvailability | true | - |
| heal.bookName | - | |
| Appears in Collections: | Μονογραφίες ( Κλειστές) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Randomized and Approximation Algorithms for Blue-Red Matching.pdf | 328.31 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
