- Tytuł:
- Analysis of the efficiency of graph coloring algorithms
- Autorzy:
- Kubale, Marek
- Powiązania:
- https://bibliotekanauki.pl/articles/748571.pdf
- Data publikacji:
- 1982
- Wydawca:
- Polskie Towarzystwo Matematyczne
- Tematy:
-
Computational complexity and efficiency of algorithms
Coloring of graphs and hypergraphs
Graph theory - Opis:
-
.
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. - Źródło:
-
Mathematica Applicanda; 1982, 10, 19
1730-2668
2299-4009 - Pojawia się w:
- Mathematica Applicanda
- Dostawca treści:
- Biblioteka Nauki
Artykuł