An Optimal Solution for the Channel-Assignment Problem
- 1 November 1979
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-28 (11), 807-810
- https://doi.org/10.1109/tc.1979.1675260
Abstract
Given a set of intervals (pairs of real numbers), we look at the problem of finding a minimal partition of this set such that no element of the partition contains two overlapping intervals. We exhibit a Θ(N log N) algorithm which is optimal. The problem has applications in LSI layout design and job scheduling.Keywords
This publication has 6 references indexed in Scilit:
- Optimal Expected-Time Algorithms for Closest Point ProblemsACM Transactions on Mathematical Software, 1980
- Minimal Resources for Fixed and Variable Job SchedulesOperations Research, 1978
- Geometric intersection problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- Automated printed circuit routing with a stepping apertureCommunications of the ACM, 1969
- A Characterization of Comparability Graphs and of Interval GraphsCanadian Journal of Mathematics, 1964
- A Decomposition Theorem for Partially Ordered SetsAnnals of Mathematics, 1950