Genetic Algorithms and Book Embeddings:A Dual Layered Approach

23rd Midwest Artificial Intelligence and Cognitive Science Conference 2012

Shannon Overbay ; Paul De Palma ; Marshall Hurson ; Tiffany Arnold ; Andrew Pierce

Others  :  http://ceur-ws.org/Vol-841/submission_14.pdf

来源: CEUR

【 摘 要 】

The genetic algorithm (GA) has been appliedto a wide variety of problems where trulyoptimal solutions are computationallyintractable.One such problem is the bookembedding problem from graph theory.Abook embedding is an ordering of verticesalong a line (the spine) with the edgesembedded in half-planes (the pages) extrudingfrom the line so that the edges do not cross. The goal is to find the minimal number of half-planes needed to embed a given graph.Thisproblem is known to be NP-complete.Thepaper shows that the GA can be used togenerate counter-examples to conjectured minimum bounds.