THE COMPLEXITY OF COLORING CIRCULAR ARCS AND CHORDS

被引：248

作者：

GAREY, MR ^{[1
]}

JOHNSON, DS ^{[1
]}

MILLER, GL ^{[1
]}

PAPADIMITRIOU, CH ^{[1
]}

机构：

[1] MIT, CAMBRIDGE, MA 02139 USA

来源：

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS | 1980年 / 1卷 / 02期

关键词：

D O I：

10.1137/0601025

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

引用

页码：216 / 227

页数：12

共 12 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2]

Even S., 1971, THEORY MACHINES COMP, P71, DOI DOI 10.1016/B978-0-12-417750-5.50011-7

[3]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[4]

Garey M.R., 1979, COMPUTERS INTRACTABI

[5]

Gavril F., 1974, NETWORKS, V4, P357

[6]

Gavril F., 1973, NETWORKS, V3, P261, DOI DOI 10.1002/NET.3230030305

[7] WHAT ARE INTERSECTION GRAPHS OF ARCS IN A CIRCLE [J].

KLEE, V .

[8]

Knuth D. E., 1973, ART COMPUTER PROGRAM

[9] MATRIX CHARACTERIZATIONS OF CIRCULAR-ARC GRAPHS [J].

TUCKER, A .

[10]

Tucker A., 1974, Discrete Mathematics, V7, P167, DOI 10.1016/S0012-365X(74)80027-0