An Optimal Solution for the Channel-Assignment Problem

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

Research output: Contribution to journalArticlepeer-review

109 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 languageEnglish (US)
Pages (from-to)807-810
Number of pages4
JournalIEEE Transactions on Computers
VolumeC-28
Issue number11
DOIs
StatePublished - Nov 1979

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

Fingerprint

Dive into the research topics of 'An Optimal Solution for the Channel-Assignment Problem'. Together they form a unique fingerprint.

Cite this