The theory of elementary landscapes

✍ Scribed by J.W. Barnes; B. Dimova; S.P. Dokov; A. Solomon

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 438 KB
• Volume: 16
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/s0893-9659(03)80054-x

✦ Synopsis

When joined to a stipulated neighborhood digraph, an objective function defined on the solution space of a real combinatorial optimization problem forms a landscape. Grover shows that landscapes satisfying a certain difference equation have properties favorable to local search.

Studying only symmetric and regular neighborhood digraphs, Stadler defines elementary landscapes as those which can be realized as an eigenvector of the Laplacian of the neighborhood digraph, and shows that such landscapes satisfy Grover's difference equation.

Recent developments in algebraic graph theory support a new definition of the graph Laplacian which we use to extend the notion ()f elementary landscapes to neighborhood digraphs which may be neither regular nor symmetric. This paper uses the new definition to extend the notion of elementary landscapes so that they characterize landscapes satisfying Grover's wave equation.

We extend some known results to these more general elementary landscapes and analyse the types which may occur. (~) 2003 Elsevier Science Ltd. All rights reserved.