Solving graph partitioning problems with parallel metaheuristics
Authors:
- Zbigniew Kokosiński,
- Marcin Bała
Abstract
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.
- Record ID
- CUTa5442c1ab4ff4422a48d17ecf340586e
- Publication categories
- ; ;
- Author
- Pages
- 89-105
- Other elements of collation
- tab.; Bibliografia (na s.) - 104-105; Bibliografia (liczba pozycji) - 22; Oznaczenie streszczenia - Abstr.
- Book
- Fidanova Stefka Stefka Fidanova (eds.): Recent advances in computational optimization : results of the Workshop on Computational Optimization WCO 2016, Studies in Computational Intelligence, no. 717, 2018, Cham, Springer, Springer, ISBN 978-3-319-59860-4
- Keywords in English
- simulated annealing, tabu search, parallel metaheuristic, hybrid metaheuristic, graph partitioning problem, graph partitioning number
- DOI
- DOI:10.1007/978-3-319-59861-1_6 Opening in a new tab
- URL
- https://link.springer.com/chapter/10.1007%2F978-3-319-59861-1_6 Opening in a new tab
- Language
- eng (en) English
- Score (nominal)
- 20
- Publication indicators
- = 5
- Citation count
- 5
- Additional fields
- Indeksowana w: Web of Science, Scopus, CORE
- Uniform Resource Identifier
- https://cris.pk.edu.pl/info/article/CUTa5442c1ab4ff4422a48d17ecf340586e/
- URN
urn:pkr-prod:CUTa5442c1ab4ff4422a48d17ecf340586e
* presented citation count is obtained through Internet information analysis, and it is close to the number calculated by the Publish or PerishOpening in a new tab system.