AN O(N2) ALGORITHM FOR COLORING PROPER CIRCULAR ARC GRAPHS

被引：32

作者：

ORLIN, JB

BONUCCELLI, MA

BOVET, DP

机构：

[1] UNIV PISA,IST SCI INFORMAZIONE,I-56100 PISA,ITALY

[2] UNIV ROME,IST MATEMAT GUIDO CASTENUDVO,I-00100 ROME,ITALY

来源：

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS | 1981年 / 2卷 / 02期

关键词：

D O I：

10.1137/0602012

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

引用

页码：88 / 93

页数：6

共 11 条

[1]

[Anonymous], 1975, P 7 ANN ACM S THEOR

[2] CYCLIC SCHEDULING VIA INTEGER PROGRAMS WITH CIRCULAR ONES [J].

BARTHOLDI, JJ ;

ORLIN, JB ;

RATLIFF, HD .

OPERATIONS RESEARCH, 1980, 28 (05) :1074-1085

[3]

Bellman R., 1958, Q APPL MATH, V16, P87

[4] MINIMUM NODE DISJOINT PATH COVERING FOR CIRCULAR-ARC GRAPHS [J].

BONUCCELLI, MA ;

BOVET, DP .

INFORMATION PROCESSING LETTERS, 1979, 8 (04) :159-161

[5] THE COMPLEXITY OF COLORING CIRCULAR ARCS AND CHORDS [J].

GAREY, MR ;

JOHNSON, DS ;

MILLER, GL ;

PAPADIMITRIOU, CH .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1980, 1 (02) :216-227

[6]

Gavril F., 1974, NETWORKS, V4, P357

[7]

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

[8]

ORLIN JB, UNPUBLISHED

[9]

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

[10] EFFICIENT TEST FOR CIRCULAR-ARC GRAPHS [J].

TUCKER, A .

SIAM JOURNAL ON COMPUTING, 1980, 9 (01) :1-24

← 1 2 →