Solving Graph Partitioning Problems with Parallel Metaheuristics

被引:4
|
作者
Kokosinski, Zbigniew [1 ]
Bala, Marcin [2 ]
机构
[1] Cracow Univ Technol, Fac Elect & Comp Engn, Ul Warszawska 24, PL-31155 Krakow, Poland
[2] Salumanus Sp Zoo, Ul Walerego Slawka 8a, PL-30633 Krakow, Poland
来源
RECENT ADVANCES IN COMPUTATIONAL OPTIMIZATION, WCO 2016 | 2018年 / 717卷
关键词
Simulated annealing; Tabu search; Parallel metaheuristic; Hybrid metaheuristic; Graph partitioning problem; Graph partitioning number;
D O I
10.1007/978-3-319-59861-1_6
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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 psi(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.
引用
收藏
页码:89 / 105
页数:17
相关论文
共 50 条
  • [31] A Novel DNA-based Parallel Computation for Solving Graph Coloring Problems
    Yeh, Chung-Wei
    Wu, Kee-Rong
    2009 WRI WORLD CONGRESS ON SOFTWARE ENGINEERING, VOL 2, PROCEEDINGS, 2009, : 213 - +
  • [32] PARMETAOPT - Parallel Metaheuristics Framework for Combinatorial Optimization Problems
    Borovska, Plamenka
    Nakov, Ognian
    Lazarova, Milena
    2009 IEEE INTERNATIONAL WORKSHOP ON INTELLIGENT DATA ACQUISITION AND ADVANCED COMPUTING SYSTEMS: TECHNOLOGY AND APPLICATIONS, 2009, : 225 - 230
  • [33] Genetic algorithms in solving graph partitioning problem
    Shazely, S
    Baraka, H
    Abdel-Wahab, A
    Kamal, H
    MULTIPLE APPROACHES TO INTELLIGENT SYSTEMS, PROCEEDINGS, 1999, 1611 : 155 - 164
  • [34] Resolution in Solving Graph Problems
    Ji, Kailiang
    VERIFIED SOFTWARE: THEORIES, TOOLS, AND EXPERIMENTS, VSTTE 2016, 2016, 9971 : 166 - 180
  • [35] A study of graph partitioning schemes for parallel graph community detection
    Zeng, Jianping
    Yu, Hongfeng
    PARALLEL COMPUTING, 2016, 58 : 131 - 139
  • [36] Solving moment method problems by partitioning
    von Hagen, J
    Herschlein, A
    Wiesbeck, W
    IEEE ANTENNAS AND PROPAGATION SOCIETY INTERNATIONAL SYMPOSIUM, VOLS 1-4: TRANSMITTING WAVES OF PROGRESS TO THE NEXT MILLENNIUM, 2000, : 1826 - 1829
  • [37] A Study of Multiobjective Metaheuristics When Solving Parameter Scalable Problems
    Durillo, Juan J.
    Nebro, Antonio J.
    Coello Coello, Carlos A.
    Garcia-Nieto, Jose
    Luna, Francisco
    Alba, Enrique
    IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2010, 14 (04) : 618 - 635
  • [38] Parameterized Algorithms for Graph Partitioning Problems
    Hadas Shachnai
    Meirav Zehavi
    Theory of Computing Systems, 2017, 61 : 721 - 738
  • [39] Path optimization for graph partitioning problems
    Berry, JW
    Goldberg, MK
    DISCRETE APPLIED MATHEMATICS, 1999, 90 (1-3) : 27 - 50
  • [40] ANALYSIS OF A CLASS OF GRAPH PARTITIONING PROBLEMS
    BERTOLAZZI, P
    LUCERTINI, M
    SPACCAMELA, AM
    RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1982, 16 (03): : 255 - 261