On Transforming Graph Theoretical Problems into Optimization Problems and Solution using CNN-based Analog Computing
Conference: ISTET 2009 - VXV International Symposium on Theoretical Engineering
06/22/2009 - 06/24/2009 at Lübeck, Germany
Proceedings: ISTET 2009
Pages: 5Language: englishTyp: PDF
Personal VDE Members are entitled to a 10% discount on this title
Authors:
Tuan, Do Trong (Hanoi University of Technology)
Chedjou, Jean Chamberlain; Kyamakya, Kyandoghere (University of Klagenfurt)
Abstract:
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.