FINDING THE CONNECTED COMPONENTS AND A MAXIMUM CLIQUE OF AN INTERSECTION GRAPH OF RECTANGLES IN THE PLANE

被引：126

作者：

IMAI, H ^{[1
]}

ASANO, T ^{[1
]}

机构：

[1] UNIV TOKYO, FAC ENGN, DEPT MATH ENGN & INSTRUMENTAT PHYS, TOKYO 113, JAPAN

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 1983年 / 4卷 / 04期

关键词：

D O I：

10.1016/0196-6774(83)90012-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：310 / 323

页数：14

共 12 条

[1] Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st
[2] OPTIMAL PACKING AND COVERING IN THE PLANE ARE NP-COMPLETE
FOWLER, RJ
PATERSON, MS
TANIMOTO, SL
[J]. INFORMATION PROCESSING LETTERS, 1981, 12 (03) : 133 - 137
[3] Gacril F., 1977, 11TH P C INF SCI SYS, P91
[4] GALIL Z, 1979, 11TH P ANN ACM S THE, P13
[5] Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1
[6] Golumbic M. C., 1980, ALGORITHMIC GRAPH TH
[7] FINDING CONNECTED COMPONENTS OF AN INTERSECTION GRAPH OF SQUARES IN THE EUCLIDEAN PLANE
IMAI, H
[J]. INFORMATION PROCESSING LETTERS, 1982, 15 (03) : 125 - 128
[8] Roberts F.S., 1969, RECENT PROGR COMBINA, P301
[9] CONNECTED COMPONENT LABELING USING QUADTREES
SAMET, H
[J]. JOURNAL OF THE ACM, 1981, 28 (03) : 487 - 501
[10] Shamos M. I., 1975, 16TH P IEEE S F COMP, P151, DOI DOI 10.1109/SFCS.1975.8