On Transforming Graph Theoretical Problems into Optimization Problems and Solution using CNN-based Analog Computing

Konferenz: ISTET 2009 - VXV International Symposium on Theoretical Engineering
22.06.2009 - 24.06.2009 in Lübeck, Germany

Tagungsband: ISTET 2009

Seiten: 5Sprache: EnglischTyp: PDF

Persönliche VDE-Mitglieder erhalten auf diesen Artikel 10% Rabatt

Tuan, Do Trong (Hanoi University of Technology)
Chedjou, Jean Chamberlain; Kyamakya, Kyandoghere (University of Klagenfurt)

We present a novel method for transforming graph theoretical problems into optimization problems and calculating shortest path/walk in both directed and undirected graphs. Analog Computing based on Cellular Neural Networks (CNN) paradigm is carried out to derive ultra-fast solu-tions when dealing with graphs of complex topologies. As proof of concepts of the proposed method, simulations are performed on graphs of magni-tude 11 and the results obtained show the efficiency of the novel method. The proposed method is challenging as it can be extended to solving scheduling issues in real-world scenarios which are NP-hard problems.