Randomized and Approximation Algorithms for Blue-Red Matching
Randomized and Approximation Algorithms for Blue-Red Matching
复制标题
蓝红匹配的随机和近似算法
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
S. Zachos
中科院分区：
文献类型：
--
作者：
C. Nomikos;Aris Pagourtzis;S. Zachos
我们引入了蓝-红匹配问题：给定一个有红边和蓝边的图，边界为w，求出每种颜色最多w条边组成的最大匹配。我们表明，蓝-红匹配至少与精确匹配问题一样困难（Papadimitriou和Yannakakis， 1982），对于精确匹配问题，它是否可以在多项式时间内解决仍然是开放的。我们提出了一种RNC算法以及两种快速逼近算法。我们最后展示了我们的结果适用于路由和分配波长的问题，以最大数量的请求在全光环。
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 (Papadimitriou 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.