Solving graph partitioning problems with parallel metaheuristics / Zbigniew Kokosiński, Marcin Bała // W: Recent advances in computational optimization : results of the Workshop on Computational Optimization ... więcej

Solving graph partitioning problems with parallel metaheuristics / Zbigniew Kokosiński, Marcin Bała // W: Recent advances in computational optimization : results of the Workshop on Computational Optimization WCO 2016 / ed. Stefka Fidanova. – Cham : Springer, 2018. – (Studies in Computational Intelligence, ISSN 1860-949X ; 717). – S. 89-105 : tab. – Bibliogr. 22 poz., Abstr. – Mat. konf.: WCO 2016, Gdansk, Poland, 11-14.09.2016. – doi: 10.1007/978-3-319-59861-1_6. – ISBN 978-3-319-59860-4. – ISBN 978-3-319-59861-1 (eBook)

In this article we describe computer experiments while testing a family of parallel and hybrid metaheuristics against a small set of graph partitioning problems like clustering, partitioning into cliques ... więcej

In this article we describe computer experiments while testing a family of parallel and hybrid metaheuristics against a small set of graph partitioning problems like clustering, partitioning into cliques and coloring. In all cases the search space is composed of vertex partitions satisfying specific problem requirements. The solver application contains two sequential and nine parallel/hybrid algorithms developed on the basis of SA and TS metaheuristics. A number of tests are reported and conclusions concerning metaheuristics' performance that result from the conducted experiments are derived. The article provides a case study in which partitioning numbers ψ_k(G), k ≥ 2, of DIMACS graph coloring instances are evaluated experimentally by means of H-SP metaheuristic which is found to be the most efficient in terms of solution quality.