Advances in the enumeration of foldable self-avoiding walks
by Christophe Guyeux; Jean-Claude Charr; Jacques Bou Abdo; Jacques Demerjian
International Journal of Computational Science and Engineering (IJCSE), Vol. 22, No. 4, 2020

Abstract: Self-avoiding walks (SAWs) have been studied for a long time due to their intrinsic importance and the many application fields in which they operate. A new subset of SAWs, called foldable SAWs, has recently been discovered when investigating two different SAW manipulations embedded within existing protein structure prediction (PSP) software. Since then, several attempts have been made to find out more about these walks, including counting them. However, calculating the number of foldable SAWs appeared as a tough work, and current supercomputers fail to count foldable SAWs of length exceeding ≈ 30 steps. In this article, we present new progress in this enumeration, both theoretical (mathematics) and practical (computer science). A lower bound for the number of foldable SAWs is firstly proposed, by studying a special subset called prudent SAWs that is better known. The triangular and hexagonal lattices are then investigated for the first time, leading to new results about the enumeration of foldable SAWs on such lattices. Finally, a parallel genetic algorithm has been designed to discover new non-foldable SAWs of lengths ≈ 100 steps, and the results obtained with this algorithm are promising.

Online publication date: Tue, 08-Sep-2020

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Computational Science and Engineering (IJCSE):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com