Finding large cliques in sparse semi-random graphs by simple randomized search heuristics

dc.contributor.author	Storch, Tobias	de
dc.date.accessioned	2009-05-12T16:00:39Z
dc.date.available	2009-05-12T16:00:39Z
dc.date.issued	2006-06	de
dc.description.abstract	Surprisingly, general heuristics often solve hard combinatorial problems quite sufficiently, although they do not outperform specialized algorithms. Here, the behavior of simple randomized optimizers on the maximum clique problem is investigated. We focus on semi-random models for sparse graphs, in which an adversary is even allowed to insert a limited number of edges and not only to remove them. In the course of these investigations also the approximation behavior on general graphs and the optimization behavior on sparse graphs and further semi-random graph models are considered. With regard to the optimizers particular interest is given to the influences of the population size and the search operator.	en
dc.identifier.uri	http://hdl.handle.net/2003/26119
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-8712
dc.language.iso	en	de
dc.relation.ispartofseries	Reihe CI; 211-06	de
dc.subject	evolutionary algorithm	en
dc.subject	maximum clique problem	en
dc.subject	population size	en
dc.subject	randomized local search	en
dc.subject	run time analysis	en
dc.subject	semi-random graph	en
dc.subject.ddc	004	de
dc.title	Finding large cliques in sparse semi-random graphs by simple randomized search heuristics	en
dc.type	Text	de
dc.type.publicationtype	report	de
dcterms.accessRights	open access

Files

Now showing 1 - 1 of 1