AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS   Info

AG Audience

English

30 Minutes

Saarbrücken

The graph bisection problem, which is to partition the nodes of an undirected graph into two equal-sized subsets with a minimal amount of edges crossing, is known to be NP-hard. Recently, there have been works using simulated annealing and a hill-climbing algorithm on random graphs, both proven to succeed with high probability in polynomial time. In this task, two evolutionary algorithms, a (1+1)-EA as well as a simple multi-objective EA and their particular local search versions are analyzed. Therefore, the behavior on different simple graph classes is being observed in order to analyze the mean solving-time as well as to indicate advantages and disadvantages of the different algorithms.

Frank Neumann

--email hidden

passcode not visible

logged in users only