Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/66616
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Randomized local search, evolutionary algorithms, and the minimum spanning tree problem |
Author: | Neumann, F. Wegener, I. |
Citation: | Theoretical Computer Science, 2007; 378(1):32-40 |
Publisher: | Elsevier Science BV |
Issue Date: | 2007 |
ISSN: | 0304-3975 1879-2294 |
Statement of Responsibility: | Frank Neumann, Ingo Wegener |
Abstract: | Randomized search heuristics, among them randomized local search and evolutionary algorithms, are applied to problems whose structure is not well understood, as well as to problems in combinatorial optimization. The analysis of these randomized search heuristics has been started for some well-known problems, and this approach is followed here for the minimum spanning tree problem. After motivating this line of research, it is shown that randomized search heuristics find minimum spanning trees in expected polynomial time without employing the global technique of greedy algorithms. © 2006 Elsevier Ltd. All rights reserved. |
Keywords: | Minimum spanning trees Analysis of expected optimization time Parallel random search (1 + λ) |
Rights: | Copyright © 2006 Elsevier Ltd. All rights reserved. |
DOI: | 10.1016/j.tcs.2006.11.002 |
Published version: | http://dx.doi.org/10.1016/j.tcs.2006.11.002 |
Appears in Collections: | Aurora harvest Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.