DocumentCode
1138934
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
Issue
11
fYear
1979
Firstpage
807
Lastpage
810
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;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/TC.1979.1675260
Filename
1675260
Link To Document