Maximum Red/Blue Interval Matching with Applications
Maximum Red/Blue Interval Matching with Applications
复制标题
与应用匹配的最大红/蓝间隔
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Xiaodong Wu
中科院分区：
文献类型：
--
作者：
D. Chen;X. Hu;Xiaodong Wu
在本文中，我们考虑了计算n个区间的集合i之间的最大基数匹配的问题，使得i中的一对区间只有当它们彼此重叠且具有不同的颜色时才能匹配。这一问题出现在一些应用中，例如放射外科治疗计划。给出了该问题的贪婪算法，该算法在O(Nloglogn)时间内完成排序输入，并在相同的时间范围内解决了红/蓝区间匹配问题的推广.
In this paper, we consider the problem of computing a maximum cardinality matching among a set I of n intervals that are colored as either red or blue, such that a pair of intervals in I can be matched only if they overlap with each other and have different colors. This problem arises in some applications such as radiosurgery treatment planning. We present a greedy algorithm for this problem that runs in O(n log log n) time for sorted input.We also solve a useful generalization of this red/blue interval matching problem in the same time bound.