Springer
Table of ContentsAuthor IndexSearch

On the Treewidth of NK Landscapes

Yong Gao and Joseph Culberson

Department of Computing Science,
University of Alberta
Edmonton, Alberta,
Canada, T6G 2E8
{ygao,joe}@cs.ualberta.ca

Abstract. The concepts of treewidth and tree-decomposition on graphs generalize those of the trees. It is well established that when restricted to instances with a bounded treewidth, many NP hard problems can be solved polynomially. In this paper, we study the treewidth of the NK landscape models. We show that the NK landscape model with adjacent neighborhoods has a constant treewidth, and prove that for $k\geq 2$, the treewidth of the NK landscape model with random neighborhoods asymptotically grows with the problem size $n$.

LNCS 2723, p. 948 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003