AN ONLINE GRAPH-COLORING ALGORITHM WITH SUBLINEAR PERFORMANCE RATIO

被引：84

作者：

LOVASZ, L

SAKS, M

TROTTER, WT

机构：

[1] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544

[2] RUTGERS STATE UNIV,RUTGERS CTR OPERAT RES,NEW BRUNSWICK,NJ 08903

[3] BELL COMMUN RES,MORRISTOWN,NJ 07960

[4] RUTGERS STATE UNIV,DEPT MATH,NEW BRUNSWICK,NJ 08903

[5] ARIZONA STATE UNIV,DEPT MATH,TEMPE,AZ 85287

来源：

关键词：

D O I：

10.1016/0012-365X(89)90096-4

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

引用

页码：319 / 325

页数：7

共 21 条

[1] EFFECTIVE COLORATION [J].

BEAN, DR .

[2]

BENTLEY JL, IN PRESS COMMUNICATI

[3] HEURISTICS THAT DYNAMICALLY ORGANIZE DATA-STRUCTURES [J].

BITNER, JR .

[4]

BORODIN A, 1987, 19TH P ANN ACM S THE, P373

[5]

CHUNG FRK, DYNAMIC LOCATION PRO

[6]

CHUNG RRK, 1987, DISCRETE ALGORITHMS

[7]

GONNET C, 1979, 20TH P IEEE S F COMP, P169

[8]

Johnson D. S., 1974, SIAM Journal on Computing, V3, P299, DOI 10.1137/0203025

[9]

Karlin A. R., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P244, DOI 10.1109/SFCS.1986.14

[10]

KIERSTEAD H, IN PRESS SIAM J DISC