請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38420
標題: On 2-Dimensional Channel Assignment Problem
作者: D.T.Lee
J.Y.T.Leung
出版社: IEEE Computer Society Washington, DC, USA
摘要: 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.
URI: http://hdl.handle.net/11455/38420
ISSN: 0018-9340
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。