Book chapter
Maximum Red/Blue Interval Matching with Application
Computing and Combinatorics, pp.150-158
Lecture Notes in Computer Science, Springer Berlin Heidelberg
07/31/2001
DOI: 10.1007/3-540-44679-6_17
Abstract
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.
Details
- Title: Subtitle
- Maximum Red/Blue Interval Matching with Application
- Creators
- Danny Z ChenXiaobo Sharon HuXiaodong Wu
- Resource Type
- Book chapter
- Publication Details
- Computing and Combinatorics, pp.150-158
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/3-540-44679-6_17
- ISSN
- 0302-9743
- Language
- English
- Date published
- 07/31/2001
- Academic Unit
- Electrical and Computer Engineering; Radiation Oncology
- Record Identifier
- 9984047746902771
Metrics
9 Record Views