Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Evolutionary approach to obtain graph covering by densely connected subgraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
This article describes two evolutionary methods for dividing a graph into densely connected structures. The first method deals with the clustering problem, where the element order plays an important role. This formulation is very useful for a wide range of Decision Support System (DSS) applications. The proposed clustering method consists of two stages. The first is the stage of data matrix reorganization, using a specialized evolutionary algorithm. The second stage is the final clustering step and is performed using a simple clustering method (SCM). The second described method deals with a completely new partitioning algorithm, based on the subgraph structure we call α-clique. The α-clique is a generalization of the clique concept with the introduction of parameter α, which imposes for all vertices of the subgraph the minimal percentage (α*100%) of vertices of this subgraph that must be connected with vertices of this α-clique. Traditional clique is an instance of α-clique with α = 1. Application of this parameter makes it possible to control the degree (or strength) of connections among vertices (nodes) of this subgraph structure. The evolutionary approach is proposed as a method that enables finding separate α-cliques that cover the set of graph vertices.
Słowa kluczowe
Opis fizyczny
Bibliogr. 35 poz., il.
  • Aho, A.V., Hopcroft, J.E. and Ullman, J.D. (1974) The Design and Analysis of Computer Algorithms. Addison-Wesley.
  • Altus, S.S., Kroo, I.M. and Gage, P.J. (1996) A Genetic Algorithm for Scheduling and Decomposition of Multidisciplinary Design Problems. J. of Mechanical Design, 118(4), 486-489.
  • Aussiello,G., Crescenzi, P., Gambosi,G., Kann,V., Marchetti-Spaccamela, A. and Protasi, M. (1999) Complexity and Approximation. Springer.
  • Bagirov, A.M. and Yearwood, J. (2006) A new non-smooth optimization algorithm for minimum sum-of-squares clustering problems. EJOR 170, 578-595.
  • Benson, S.J. and Ye, Y. (2000) Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation. In: M. Ferris and J. Pang, eds., Applications and Algorithms of complementarity. Kluwer Academic Publishers, 1-18.
  • Beineke, L. and Wilson, R. (1978) Selected Topics in Graph Theory. Academic Press.
  • Browning, T.R. (2001) Applying the Design Structure Matrix to System Decomposition and Integration Problems: A Review and New Directions. IEEE Transactions on Engineering Management, 48(3), 292-306.
  • Chen, Z.-Q., Wang, R.-L. and Okazaki, K.(2008) An Efficient Genetic AlgorithmBased Approach for the Minimum Graph Bisection Problem. IJCSNS International Journal of Computer Science and Network Security, 8(6), 118-124.
  • Cichosz, P. (2000) Systemy uczce się (Learning systems, in Polish). WNT, Warszawa.
  • Cowen, L. (1998) Approximation Algorithms. John Hopkins University.
  • Falkner, J., Rendl, F. and Wolkowicz, H. (1994) A computational study of graph partitioning. Mathematical Programming, 66 (2), 211-239.
  • Hansen, P., Mladenovic, N. and Urosevic, D. (2004) Variable neighborhood search for the maximum clique. The Fourth International Colloquium on Graphs and Optimisation (GO-IV), 145 (1), 117-125.
  • Hassin, R. and Khuller, S. (1986) z-Approximation. Journal of Algorithms, 41 (2), 429-442.
  • Hochbaum, D.S., ed. (1997) Approximation Algorithms for NP.-hard Problems PWS Publishing Company.
  • Hromkovic, J. (2001) Algorithmics for Hard Problems. Springer.
  • Jain, A.K. and Dubes, R.C. (1988) Algorithms for Clustering Data. Eaglewood Cliffs, NJ, Prentice-Hall.
  • Jukna, S. (2001) Extremal Combinatorics. Springer-Verlag, Berlin-Heidelberg.
  • Korte, B. and Vygen, J. (2000) Combinatorial Optimization, Theory and Algorithms. Springer.
  • Kumlander, D. (2007) An Approach for the Maximum Clique Finding Problem, Test Tool Software Engineering. Software Engineering, Innsbruck, Austria.
  • Lenstra, J.K. (1977) Sequencing by enumerative methods. Mathematical Centre Tracts, Amsterdam.
  • Marchiori, E. (1998) A Simple Heuristic Based Genetic Algorithm for the Maximum Clique Problem. Proceedings of the 1998 ACM Symposium on Applied Computing. ACM, 366-373.
  • McCulley, C. and Bloebaum, C.A. (1996) Genetic Tool for Optimal Design Sequencing in Complex Engineering Systems. Structural Optimization, 12 (2-3), 186-201.
  • McCormick, W.T., Schweitzer, P.J. and White, T.W. (1972) Problem decomposition and data reorganization by a clustering technique. Operations Res. 20, 993-1009.
  • Michalewicz, Z. (1996) Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, Berlin-Heidelberg
  • Mulawka, J. and Stańczak, J. (1999) Genetic Algorithms with Adaptive Probabilities of Operators Selection. Proceedings of ICCIMA’99, New Delhi, India. World Scientific, 464-468.
  • Potrzebowski, H., Stańczak, J. and Sęp, K. (2004) Evolutionary metod in grouping of units with argument reduction. Proceedings of the 15th International Conference on Systems Science vol. 3. Oficyna Wydawnicza Politechniki Wrocławskiej, 29-3-6.
  • Potrzebowski, H., Stańczak, J. and Sęp, K. (2006) Evolutionary Algorithm to Find Graph Covering Subsets Using -Cliques, In: J. Arabas, ed., Evolutionary Computation and Global Optimization, Prace Naukowe Politechniki Warszawskiej, 351-358.
  • Protasi, M. (2001) Reactive local search for the maximum clique problem. Algorithmica, 29(4), 610-637.
  • Rogers, J.L. (1997) Reducing Design Cycle Time and Cost Through Process Resequencing. International Conference on Engineering Design ICED 1997, Tampere, Finland, Estonian Academy Publishers.
  • Stańczak, J. (2003) Biologically inspired methods for control of evolutionary algorithms, Control and Cybernetics. 32(2), 411-433.
  • Sysło, M.M., Deo, N. and Kowalik, J.S. (1983) Algorithms of Discrete Optimization. Prentice-Hall.
  • Talbi, E.-G. and Bessiere, P. (1991) A parallel genetic algorithm for the graph partitioning problem. Proc. of the 5th International conference on Supercomputing. ACM, New York, 312-320.
  • Williamson, D. (1999) Lecture Notes on Approximation Algorithms. IBM Research Report RC 21409 02 17.
  • Wilson, R.J. (1996) Introduction to Graph Theory. Addison Wesley Longman.
  • Yu, T.L., Goldberg, D.E., Yassine, A. and Yassine, C. (2003) A Genetic Algorithm Design Inspired by Organizational Theory. Genetic and Evolutionary Computation Conference (GECCO) 2003, Chicago, Illinois. Springer-Verlag, Heidelberg, LNCS 2724, 1620-1621.
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.