Zastosowanie algorytmów rojowych do kolorowania grafów

• Autorzy: Obszarski P. , Piwakowski K.

Warianty tytułu

EN

Applying PSO paradigm to graph coloring

• Konferencja: XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
• Języki publikacji: PL

Abstrakty

PL

Przedstawiamy sposób adaptacji heurystycznej metody przeszukiwania PSO (ang. Particle Swarm Optimization) do znajdowania suboptymalnych pokolorowań wierzchołkowych grafów prostych. Prezentujemy sposób przeprowadzenia eksperymentów obliczeniowych oraz ich wyniki.

EN

Adaptation of the Particle Swarm Optimization method for obtaining suboptimal vertex colorings of graphs is proposed. We present details of performed computational experiments and their results.

Słowa kluczowe

PL

graf; kolorowanie grafów; kolorowanie wierzchołków; algorytm rojowy

EN

graph; graph coloring; vertex coloring; PSO paradigm

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 143
• Strony: 107--113
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Obszarski P.

autor

Piwakowski K.

• Katedra Algorytmów i Modelowania Systemów Politechniki Gdańskiej, 80-952 Gdańsk Wrzeszcz, ul. Gabriela Narutowicza 11/12, tel.: [phone],

Bibliografia

• 1. Aho A. V. et. al.: The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, Reading, Massachusetts 1974.
• 2. Eberhart R. C, Kennedy C: Particle swarm optimization. Proceedings of the 1995 IEEE International Conference on Neural Networks, IEEE Press, Vol. 4, 1995, p. 1942-1948.
• 3. Kubale M., Manuszewski K.: The smallest hard-to-color graphs for the classical, total and strong colorings of vertices. Control and Cybernetics, Vol. 28, No. 2, 1999, p. 355-365.
• 4. Kubale M., Pakulski J., Piwakowski K.: The smallest hard-to-color graph for the SL algorithm. Disc. Math, 164, 1997, pp. 197-212.
• 5. Matula D. W. et. al.: Graph Coloring Algorithms, Graph Theory and Computing. Academic Press, New York 1972, p. 109-122.
• 6. Powell M. B., Welsh P. J.: An upper bound for the chromatic number of graph and its applications to timetabling problem. Comput. J. 10, 1967, p. 85-86.