Parallel simulated annealing algorithm for graph coloring problem / Szymon Łukasik, Zbigniew Kokosiński, Grzegorz Świętoń // W: Parallel Processing and Applied Mathematics : 7th International Conference, ... więcej

Parallel simulated annealing algorithm for graph coloring problem / Szymon Łukasik, Zbigniew Kokosiński, Grzegorz Świętoń // W: Parallel Processing and Applied Mathematics : 7th International Conference, PPAM 2007, Gdansk, Poland, September 9-12, 2007 : revised selected papers [Dokument elektroniczny] / eds. R. Wyrzykowski [et al.]. – Berlin ; Heidelberg : Springer, 2008. – (Lecture Notes in Computer Science, ISSN 1611-3349 ; 4967). – S. 229-238 : tab. – Tryb dostępu: https://link.springer.com/chapter/10.1007%2F978-3-540-68111-3_25. – Bibliogr. 26 poz., Abstr. – doi: 10.1007/978-3-540-68111-3_25. – ISBN 978-3-540-68111-3 (online). – ISBN 978-3-540-68105-2 (print)

The paper describes an application of Parallel Simulated Annealing (PSA) for solving one of the most studied NP-hard optimization problems: Graph Coloring Problem (GCP). Synchronous master-slave model ... więcej

The paper describes an application of Parallel Simulated Annealing (PSA) for solving one of the most studied NP-hard optimization problems: Graph Coloring Problem (GCP). Synchronous master-slave model with periodic solution update is being used. The paper contains description of the method, recommendations for optimal parameters settings and summary of results obtained during algorithm’s evaluation. A comparison of our novel approach to a PGA metaheuristic proposed in the literature is given. Finally, directions for further work in the subject are suggested.