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

The computation of generalized median graphs (the graph with the smallest average edit distance to all graphs in a given set of graphs) is highly computationally complex. As a matter of fact, it is exponential in the number of nodes of the union of all graphs under consideration. Thus, the generalized median graph computation problem seems to be a suitable and challenging testbed for a comparison of combinatorial search and genetic algorithms. Two solutions are described in this paper. The first is an exact algorithm based on combinatorial search, while the second is a genetic algorithm. Both approaches are compared to each other in a series of experiments. (C) 1999 Elsevier Science B.V. All rights reserved.