PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1982 | 10 | 19 |
Tytuł artykułu

Analysis of the efficiency of graph coloring algorithms

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
PL
.
EN
This paper discusses the computational efficiency and the number of colors used by the following algorithms for coloring vertices of graphs: sequential coloring and sequential coloring with interchange algorithms for a largest-first and a smallest-last orderings of vertices, the coloring-pairs algorithm, and the approximately maximum independent set algorithm. Each algorithm is supplied with a Pascal-like program, time complexity in terms of the size of a graph, and worst-case behaviour. In conclusion, some computational results are included with support the estimations and suggest the sequential coloring with interchange algorithm for a largest-first vertex ordering as a method which uses the least number of colors for uniformly distributed random graphs.
Rocznik
Tom
10
Numer
19
Opis fizyczny
Daty
wydano
1982
online
1982-02-01
Twórcy
autor
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ojs-doi-10_14708_ma_v10i19_1531
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.