Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: hard-to-color graph

Sortuj według:

Ogranicz wyniki do:

A survey of hard-to-color graphs for off-line and on-line model of vertex coloring

Borowiecki P., Kubale M.

Journal of Applied Computer Science

2001

Vol. 9, nr 2

7-17

In the paper we review the most popular on-line and off-line graph coloring algorithms. For each algorithm we give: short description. performance guarantee, the smallest HC and slightly HC graphs, positive cases and negative cases. Finally, we give the smallest benchmark for off-line sequential algorithms and the smallest weak benchmark for on-line algorithms.

The smallest hard-to-color graphs for the classical, total and strong colorings of vertices

Kubale M., Manuszewski K.

Control and Cybernetics

1999

Vol. 28, no 2

355-365

: Let A(G) be the number of colors used by algorithm to color the vertices of graph G. A graph G is said to be hard-to-color (HC) (resp. slightly HC) if for every (resp. some) implementation of the algorithm A we have A(G) > chi(G), where chi(G) is the chromatic number of G. The study of HC graphs makes it possible design improved algorithms trying to avoid hard instances as far possible. Hard-to-color graphs are also good benchmarks for the evaluation of existing and future algorithms and provide an alternative way of assessing their quality. In this paper we demonstrate the smallest HC graphs for the best known coloring heuristics in classical applications, as well as when adapted to the chromatic sum coloring and strong coloring of vertices.