Title :
An Optimal Solution for the Channel-Assignment Problem
Author :
Gupta, Udaiprakash I. ; Lee, D.T. ; Leung, Joseph Y -T
Author_Institution :
Department of Electrical Engineering and Computer Science, Northwestern University
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 :
Channel-assignment problem; LSI layout design; analysis of algorithms; job scheduling; Algorithm design and analysis; Integrated circuit interconnections; Job design; Large scale integration; Partitioning algorithms; Printed circuits; Processor scheduling; Scheduling algorithm; Wire; Channel-assignment problem; LSI layout design; analysis of algorithms; job scheduling;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1979.1675260
