Geodesic
Online coloring known graphs
The electronic journal of combinatorics, Tome 7 (2000)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The problem of online coloring an unknown graph is known to be hard. Here we consider the problem of online coloring in the relaxed situation where the input must be isomorphic to a given known graph. All that foils a computationally powerful player is that it is not known to which sections of the graph the vertices to be colored belong. We show that the performance ratio of any online coloring algorithm with advance knowledge of the input graph is at least $\Omega(N/\log^2 N)$, where $N$ is the number of vertices. This matches and generalizes the bound for the case of an unknown input graph. We also show that any online independent set algorithm has a performance ratio at least $N/8$.
DOI : 10.37236/1485
Classification : 05C15, 68W25
Mots-clés : graph coloring, online algorithms, online coloring, performance ratio, online independent set algorithm 
@article{10_37236_1485,
     author = {M. M. Halld\'orsson},
     title = {Online coloring known graphs},
     journal = {The electronic journal of combinatorics},
     year = {2000},
     volume = {7},
     doi = {10.37236/1485},
     zbl = {0940.05030},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1485/}
}
TY  - JOUR
AU  - M. M. Halldórsson
TI  - Online coloring known graphs
JO  - The electronic journal of combinatorics
PY  - 2000
VL  - 7
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1485/
DO  - 10.37236/1485
ID  - 10_37236_1485
ER  - 
%0 Journal Article
%A M. M. Halldórsson
%T Online coloring known graphs
%J The electronic journal of combinatorics
%D 2000
%V 7
%U http://geodesic.mathdoc.fr/articles/10.37236/1485/
%R 10.37236/1485
%F 10_37236_1485
M. M. Halldórsson. Online coloring known graphs. The electronic journal of combinatorics, Tome 7 (2000). doi: 10.37236/1485

Cité par Sources :