Randomized and approximation algorithms for blue-red matching

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.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.access	campus
heal.bibliographicCitation	Βιβλιογραφία: σ. 724-725	el
heal.bookName	-
heal.fullTextAvailability	true
heal.generalDescription	715-725 σ.	el
heal.language	en
heal.publicationDate	2007
heal.publisher	Springer Berlin / Heidelberg	en
heal.recordProvider	Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής	el
heal.type	bookChapter
heal.type.el	Κεφάλαιο βιβλίου	el
heal.type.en	Book chapter	en

Αρχεία

Προβολή: 1 - 1 of 1