An Evolutionary Formulation of the Crossing Number Problem | Zendy

Che Sheng Gan | Zendy; Wee Chiat Alan Tan | Zendy; Voon Chet Koo | Zendy; Kwang Hwai Mak | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An Evolutionary Formulation of the Crossing Number Problem

Author(s) -

Che Sheng Gan,

Wee Chiat Alan Tan,

Voon Chet Koo,

Kwang Hwai Mak

Publication year - 2009

Publication title -

discrete dynamics in nature and society

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.264

H-Index - 39

eISSN - 1607-887X

pISSN - 1026-0226

DOI - 10.1155/2009/154015

Subject(s) - crossing number (knot theory) , conjecture , computer science , evolutionary algorithm , graph , algorithm , scheme (mathematics) , level crossing , mathematics , mathematical optimization , theoretical computer science , combinatorics , archaeology , history , mathematical analysis , intersection (aeronautics) , engineering , aerospace engineering

A graph drawing algorithm is presented which results in complete graphs having minimum crossings equal to that of Guy's conjecture. It is then generalized and formulated in an evolutionary algorithm (EA) to perform constrained search for the crossing numbers. The main objective of this work is to present a suitable two-dimensional scheme which can greatly reduce the complexity of finding crossing numbers by using computer. Program performance criteria are presented and discussed. It is shown that the EA implementation provides good confirmation of the predicted crossing numbers

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research