Combinatorial search versus genetic algorithms: A case study based on the generalized median graph problem

摘要

The computation of generalized median graphs (the graph with thesmallest average edit distance to all graphs in a given set ofgraphs) is highly computationally complex. As a matter of fact, it isexponential in the number of nodes of the union of all graphs underconsideration. Thus, the generalized median graph computation problemseems to be a suitable and challenging tested for a comparison ofcombinatorial search and genetic algorithms. Two solutions aredescribed in this paper. The first is an exact algorithm based oncombinatorial search, while the second is a genetic algorithm. Bothapproaches are compared to each other in a series of experiments.