An Optimal Solution for the Channel-Assignment Problem

Udaiprakash I. Gupta; D. T. Lee; Joseph Y.T. Leung

doi:10.1109/TC.1979.1675260

An Optimal Solution for the Channel-Assignment Problem

Udaiprakash I. Gupta, D. T. Lee, Joseph Y.T. Leung

Research output: Contribution to journal › Article › peer-review

116 Scopus citations

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.

Original language	English (US)
Pages (from-to)	807-810
Number of pages	4
Journal	IEEE Transactions on Computers
Volume	C-28
Issue number	11
DOIs	https://doi.org/10.1109/TC.1979.1675260
State	Published - Nov 1979
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Hardware and Architecture
Computational Theory and Mathematics

Keywords

Channel-assignment problem
LSI layout design
analysis of algorithms
job scheduling

Access to Document

10.1109/TC.1979.1675260

Cite this

@article{b4ab86877d6a4869ae2101b517840e43,

title = "An Optimal Solution for the Channel-Assignment Problem",

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",

author = "Gupta, {Udaiprakash I.} and Lee, {D. T.} and Leung, {Joseph Y.T.}",

year = "1979",

month = nov,

doi = "10.1109/TC.1979.1675260",

language = "English (US)",

volume = "C-28",

pages = "807--810",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "11",

}

TY - JOUR

T1 - An Optimal Solution for the Channel-Assignment Problem

AU - Gupta, Udaiprakash I.

AU - Lee, D. T.

AU - Leung, Joseph Y.T.

PY - 1979/11

Y1 - 1979/11

N2 - 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.

AB - 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.

KW - Channel-assignment problem

KW - LSI layout design

KW - analysis of algorithms

KW - job scheduling

UR - http://www.scopus.com/inward/record.url?scp=0018547323&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0018547323&partnerID=8YFLogxK

U2 - 10.1109/TC.1979.1675260

DO - 10.1109/TC.1979.1675260

M3 - Article

AN - SCOPUS:0018547323

SN - 0018-9340

VL - C-28

SP - 807

EP - 810

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 11

ER -

An Optimal Solution for the Channel-Assignment Problem

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this