How good can ants color graphs?

Aleksander Vesel (Avtor), Janez Žerovnik (Avtor)

Povzetek

V notici primerjamo algoritem Coste in Hertza, algoritem "mravlje", s postopkom zaporednega barvanja (RLF, recursive largest first) in z algoritmom tipa Petforf-Welsh. V naših poskusih je zadnji precej boljši od prvih dveh.

Ključne besede

matematika;teorija grafov;barvanje grafov;postopek zaporednega barvanja;algoritem mravlje;Petford-Welsh;RLF;mathematics;graph theory;graph coloring;ants algorithm;

Podatki

Jezik:	Angleški jezik
Leto izida:	1998
Tipologija:	0 - Ni določena
Organizacija:	UM FS - Fakulteta za strojništvo
UDK:	519.17
COBISS:	8367449
ISSN:	1318-4865
Št. ogledov:	889
Št. prenosov:	29
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	Kako dobro lahko mravlje barvajo grafe?
Sekundarni povzetek:	We compare the ants algorithm for graph coloring recently proposed by Costa and Hertz with the repeated Recursive Largest First (RLF) algorithm and with a Petford-Welsh type algorithm. In our experiments, the later is much better then the first two.
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1-10
Letnik:	ǂLet. ǂ36
Zvezek:	ǂšt. ǂ632
Čas izdaje:	1998
ID:	65726