On the 2-Dimensional Channel Assignment Problem

D. T. Lee; Joseph Y.T. Leung

doi:10.1109/TC.1984.5009310

On the 2-Dimensional Channel Assignment Problem

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

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	2-6
Number of pages	5
Journal	IEEE Transactions on Computers
Volume	C-33
Issue number	1
DOIs	https://doi.org/10.1109/TC.1984.5009310
State	Published - Jan 1984
Externally published	Yes

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

Access to Document

10.1109/TC.1984.5009310

Cite this

@article{20d64dd592fe479995c18ef254e9ac2d,

title = "On the 2-Dimensional Channel Assignment Problem",

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

keywords = "2-dimensional channel assignment, NP-completeness, coloring problem, rectangle intersection graphs",

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

year = "1984",

month = jan,

doi = "10.1109/TC.1984.5009310",

language = "English (US)",

volume = "C-33",

pages = "2--6",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "1",

}

TY - JOUR

T1 - On the 2-Dimensional Channel Assignment Problem

AU - Lee, D. T.

AU - Leung, Joseph Y.T.

PY - 1984/1

Y1 - 1984/1

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

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

KW - 2-dimensional channel assignment

KW - NP-completeness

KW - coloring problem

KW - rectangle intersection graphs

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

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

U2 - 10.1109/TC.1984.5009310

DO - 10.1109/TC.1984.5009310

M3 - Article

AN - SCOPUS:0021124580

SN - 0018-9340

VL - C-33

SP - 2

EP - 6

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 1

ER -

On the 2-Dimensional Channel Assignment Problem

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this