Evolutionary algorithm to find graph covering subsets using α-cliques

• Autorzy: Potrzebowski H. , Stańczak J. , Sęp K.
• Konferencja: Evolutionary Computation and Global Optimization 2006 / National Conference (9 ; 31.05-2.06.2006 ; Murzasichle, Poland)
• Języki publikacji: EN

Abstrakty

EN

The article describes a new evolutionary based method to divide graph into strongly connected structures we called α-cliques. The α-clique is a generalization of a clique concept with the introduction of parameter a. Using this parameter it is possible to control the degree (or strength) of connections among vertices (nodes) of this sub-graph structure. The evolutionary approach is proposed as a method that enables to find separate a-cliques that cover the set of graph vertices.

Słowa kluczowe

EN

graph theory; clique; alpha-clique; evolutionary algorithm; EA; evolutionary computation

PL

teoria grafu; klika; alfa-klika; algorytm ewolucyjny; obliczenia ewolucyjne

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2006
• Tom: z. 156
• Strony: 351--358
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Potrzebowski H.

autor

Stańczak J.

autor

Sęp K.

• Systems Research Institute, Polish Academy of Science, Warsaw, Poland,

Bibliografia

• [1] Altus, S.S., Kroo, I.M. and Gage, P.J. A Genetic Algorithm for Scheduling and Decomposition of Multidisciplinary Design Problems. Journal of Mechanical Design, Vol. 118, No. 4, pp. 486-489, 1996.
• [2] Benson, S.J. and Ye, Y. Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation. Computational complexity: The problem of approximation, Kluwer Academic Publishers, 2000.
• [3] Browning, T.R. Applying the Design Structure Matrix to System Decomposition and Integration Problems: A Review and New Directions. IEEE Transactions on Engineering Management, Vol. 48, No 3, 2001.
• [4] Kloks, T. and Kratsch, D. Listing all minimal separators of a graph. SIAM J. COMPUT., Vol. 27, No. 3, June 1998, pp. 605-613, 1998.
• [5] Lenkstra, J.K. Sequencing by enumerative methods. In Mathematical Centre Tracts, Amsterdam, 1977.
• [6] McCulley, C. and Bloebaum, C. A Genetic Tool for Optimal Design Sequencing in Complex Engineering Systems. Structural Optimization, Vol. 12, No. 2-3, pp. 186-201, 1996.
• [7] Mulawka, J. and Stańczak, J. Genetic Algorithms with Adaptive Probabilities of Operators Selection. In Proceedings of ICCIMA'99, New Delhi, India, pp. 464-468, 1999.
• [8] Owsiński, J.W. On a new naturally indexed quick clustering method with a global objective function. In Applied Stochastic Models and Data Analysis, Vol. 6, pp. 157-171, 1990.
• [9] Potrzebowski, H., Stańczak, J. and Sęp, K. Evolutionary method in grouping of units with argument reduction. In Proceedings of the 15th International Conference on Systems Science, Vol. 3, Wrocław, Poland, pp. 29-36, 2004.
• [10] Potrzebowski, H., Stańczak, J. and Sęp, K. Evolutionary methods in grouping of units. In Proc. of the 4th International Conference on Recognition Systems CORES'05, Springer-Verlag Berlin Heidelberg, pp. 279-286, 2005.
• [11] Protasi, M. Reactive local search for the maximum clique problem. Algorithmica, vol. 29, no 4, pp. 610-637, 2001.
• [12] Rogers, J.L. Reducing Design Cycle Time and Cost Thorough Process Resequencing. International Conference on Engineering Design ICED 1997, Tampere, Finland, 1997.
• [13] Stańczak, J. Rozwój koncepcji i algorytmów dla samodoskonalących się systemów ewolucyjnych, Ph.D. Dissertation, Politechnika Warszawska, 1999.
• [14] Sysło, M.M., Deo, N. and Kowalik, J. S. Algorithms of discrete optimization, Prentice-Hall, 1983.
• [15] Wilson, R.J. Introduction to graph theory. Addison Wesley Longman 1996.
• [16] Yu, T.L., Goldberg, D.E., Yassine, A. and Yassine, C. A Genetic Algorithm Design Inspired by Organizational Theory. Genetic and Evolutionary Computation Conference (GECCO) 2003, Chicago, Illinois, USA, Publ. Springer-Verlag, Heidelberg, Lecture Notes in Computer Science, Vol. 2724/2003, pp. 1620-1621, 2003.