• DocumentCode
    1652643
  • Title

    Graph partitioning using genetic algorithms with ODPX

  • Author

    Cincotti, A. ; Cutello, V. ; Pavone, M.

  • Author_Institution
    Dept. of Math. & Comput. Sci., Catania Univ., Italy
  • Volume
    1
  • fYear
    2002
  • Firstpage
    402
  • Lastpage
    406
  • Abstract
    In this paper, we study approximate solutions to the extension of the "maximally balanced connected partition problem", whose corresponding decision problem is known to be 𝒩𝒫-complete. We introduce a genetic algorithm with a new crossover operator, called the "order- and distance-preserving crossover" (ODPX) operator, and we compare the results of our algorithm to a well-known deterministic approximation algorithm
  • Keywords
    approximation theory; computational complexity; genetic algorithms; graph theory; mathematical operators; NP-complete decision problem; ODPX operator; approximate solutions; deterministic approximation algorithm; genetic algorithms; graph partitioning; maximally balanced connected partition problem; order and distance-preserving crossover operator; Approximation algorithms; Biological cells; Computer science; Genetic algorithms; Genetic programming; Mathematics; Partitioning algorithms;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Evolutionary Computation, 2002. CEC '02. Proceedings of the 2002 Congress on
  • Conference_Location
    Honolulu, HI
  • Print_ISBN
    0-7803-7282-4
  • Type

    conf

  • DOI
    10.1109/CEC.2002.1006268
  • Filename
    1006268
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1652643