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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M.G. Andrews, M.J. Atallah, D.Z. Chen, and D.T. Lee, “Parallel algorithms for maximum matching in complements of interval graphs and related problems,” Algorithmica, 26(2) (2000), pp. 263–289.
M.G. Andrews and D.T. Lee, “An optimal algorithm for matching in interval graphs,” manuscript, 1992.
D.Z. Chen, X. Wu, L. Zhang, X. Hu, and C. Yu, “A new algorithm for intensitymodulated arc therapy (IMAT) with dynamic multileaf collimation,” manuscript, 2001.
T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, McGraw-Hill, New York, NY, 1990.
M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
J.E. Hopcroft and R.M. Karp, “An n5/2 algorithm for maximum matchings in bipartite graphs,” SIAM J. Comput., 2 (1973), pp. 225–231.
A. Moitra and R.C. Johnson, “A parallel algorithm for maximum matching in interval graphs,” Proc. Int. Conf. Parallel Processing, 1989, Vol. III, pp. 114–120.
F.P. Preparata and M.I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.
P. van Emde Boas, “Preserving order in a forest in less than logarithmic time and linear space,” Information Processing Letters, 6(3) (1977), pp. 80–82.
P. van Emde Boas, R. Kaas, and E. Zijlstra, “Design and implementation of an efficient priority queue,” Mathematical Systems Theory, 10 (1977), pp. 99–127.
C.X. Yu, personal communication, January 2001.
C.X. Yu, D. Yan, M.N. Du, S. Zhou, and L.J. Verhey, “Optimization of leaf positioning when shaping a radiation field with a multileaf collimator,#x201D; Phys. Med. Biol., 40(2) (1995), pp. 305–308.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, D.Z., Hu, X.S., Wu, X. (2001). Maximum Red/Blue Interval Matching with Application. In: Wang, J. (eds) Computing and Combinatorics. COCOON 2001. Lecture Notes in Computer Science, vol 2108. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44679-6_17
Download citation
DOI: https://doi.org/10.1007/3-540-44679-6_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42494-9
Online ISBN: 978-3-540-44679-8
eBook Packages: Springer Book Archive