how randomized search heuristics find maximum cliques in planar graphs

dc.contributor.author	Storch, Tobias	de
dc.date.accessioned	2009-05-12T16:00:17Z
dc.date.available	2009-05-12T16:00:17Z
dc.date.issued	2006-03	de
dc.description.abstract	Surprisingly, general search heuristics often solve combinatorial problems quite sufficiently, although they do not outperform specialized algorithms. Here, the behavior of simple randomized optimizers on the maximum clique problem on planar graphs is investigated rigorously. The focus is on the worst-, average-, and semi-average-case behaviors. In semi-random planar graph models an adversary is allowed to modify moderately a random planar graph, where a graph is chosen uniformly at random among all planar graphs. With regard to the heuristics particular interest is given to the influences of the following four popular strategies to overcome local optima: local- vs. global-search, single- vs. multi-start, small vs. large population, and elitism vs. non-elitism selection. Finally, the black-box complexities of the planar graph models are analyzed.	en
dc.identifier.uri	http://hdl.handle.net/2003/26111
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-9024
dc.language.iso	en	de
dc.relation.ispartofseries	Reihe CI; 203-06	de
dc.subject	analysis of algorithms and problem complexity	en
dc.subject	Theory of computation	en
dc.subject.ddc	004	de
dc.title	how randomized search heuristics find maximum cliques in planar graphs	en
dc.type	Text	de
dc.type.publicationtype	report	de
dcterms.accessRights	open access

Files

Now showing 1 - 1 of 1