Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 9

Position Papers of the 2016 Federated Conference on Computer Science and Information Systems

Testing of parallel metaheuristics for graph partitioning problems

,

DOI: http://dx.doi.org/10.15439/2016F414

Citation: Position Papers of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 9, pages 79–85 ()

Full text

Abstract. In this paper 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 resulting from the testing experiments are derived.

References

  1. G. Ausiello. et all. Complexity and Approximation - Combinatorial optimization problems and their approximability properties, Springer-Verlag, 1999.
  2. C. Blum, A. Roli, E. Alba. An Introduction to Metaheuristic Techniques. [in:] Parallel Metaheuristics, Wiley-Interscience, 3-42, 2005
  3. U. Brandes, M. Gaertler, D. Wagner Experiments on Graph Clustering Algorithms, Proc. ESA’2003, LNCS 2832, 568-579, 2003 http://dx.doi.org/10.1007/978-3-540-39658-1-52
  4. C-Y. Byun. Lower Bound for Large-Scale Set Partitioning Problems, ZIB-Report, Vol. 12, 1822, 2001
  5. I. Charon, O. Hudry. Noising methods for a clique partitioning problem. Discrete Applied Mathematics, Vol. 154, 754-769, 2006 http://dx.doi.org/10.1016/j.dam.2005.05.029
  6. L. Coslovich, R. Pesenti, W. Ukovich. Large-Scale Set Partitioning Problems. Journal on Computing, Vol. 13, 191-209, 2001
  7. B. Crawford, C. Castro. ACO with Lookahead Procedures for Solving Set Partitioning Problems and Covering Problems. Chile, 2004
  8. R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. Freeman, San Francisco, 1979
  9. X. Ji, J. E. Mitchell. The Clique Partition Problem with Minimum Clique Size Requirement, Discrete Optimization, Vol. 4, 87-102, 2007
  10. B. W. Kernighan, S. Lin. An Efficient Heuristics Procedure for Partitioning Graphs. The Bell System Technical Journal, Vol. 49, 291-307, 1970
  11. Z. Kokosiński, K. Kwarciany, M. Kołodziej. Efficient Graph Coloring with Parallel Genetic Algorithms. Computing and Informatics, Vol. 24, No. 2, 109-121, 2005
  12. M. Kubale(Ed.) Graph Colorings, American Mathematical Society, 2004
  13. M. Kubale. Some results concerning the complexity of restricted colorings of graphs. Discrete Applied Mathematics, Vol. 36, 35-46, 1992
  14. E. Mujuni, F. Rosamond. Parameterized Complexity of the Clique Partition Problem. The Australasian Theory Symposium, 75-78, 2008
  15. A. Nowosielski, P. A. Kowalski, P. Kulczycki. The column-oriented database partitioning optimization based on the natural computing algorithms Proc. FedCSIS, 1035-1041, 2015 http://dx.doi.org/10.15439/2015F262
  16. S.M. Sait, H. Youssef. Iterative computer algorithms with applications in engineering. IEEE Computer Society, Los Alamitos, 1999
  17. W-D. Tseng, I-S. Hwang, L-J. Lee, C-Z. Yang. Clique-partitioning connections-scheduling with faulty switches in dilated Benes network, Journal of the Chinese Institute of Engineers, Vol. 32, 853-860, 2009
  18. S. Zhou. Minimum partition of an independence system into independent sets, Discrete Optimization, Vol. 6, 125-133, 2009 http://dx.doi.org/10.1016/j.disopt.2008.10.001