On the 2-Dimensional Channel Assignment Problem

D. T. Lee, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

We consider the 2-dimensional channel assignment problem: given a set S of iso-oriented rectangles (whose sides are parallel to the coordinate axes), find a minimum number of planes (channels) to which only nonoverlapping rectangles are assigned. This problem is equivalent to the coloring problem of the rectangle intersection graph G = (V, E), in which each vertex in V corresponds to a rectangle and two vertices are adjacent iff their corresponding rectangles overlap, and we ask for an assignment of a minimum number of colors to the vertices such that no adjacent vertices are assigned the same color. We show that the problem is NP-hard.

Original languageEnglish (US)
Pages (from-to)2-6
Number of pages5
JournalIEEE Transactions on Computers
VolumeC-33
Issue number1
DOIs
StatePublished - Jan 1984

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • 2-dimensional channel assignment
  • NP-completeness
  • coloring problem
  • rectangle intersection graphs

Fingerprint Dive into the research topics of 'On the 2-Dimensional Channel Assignment Problem'. Together they form a unique fingerprint.

Cite this