DocumentCode :
1264939
Title :
Solving the shortest path problem using an analog network
Author :
Bu, Linkai ; Chiueh, Tzi-Dar
Author_Institution :
Dept. of Electr. Eng., Nat. Taiwan Univ., Taipei, Taiwan
Volume :
46
Issue :
11
fYear :
1999
fDate :
11/1/1999 12:00:00 AM
Firstpage :
1360
Lastpage :
1363
Abstract :
The shortest path problem is one of the most important combinatorial optimization problems. In this paper, a network consisting of variable turn-on-voltage diodes (VTDs) is proposed for tackling the shortest path problem. The network solves the shortest path problem in a parallel and distributed manner. The network itself is isomorphic to the graph in which the shortest path solution is to be sought. The proposed VTD network settles to steady-state solutions quickly and consumes very little power. It is also shown theoretically that the VTD network solves the shortest path problem exactly. A circuit implementation of the VTD network is proposed and simulation results confirm its functionality. Finally, two physical limitations of VTD´s and their effect on the performance are discussed
Keywords :
analogue circuits; circuit optimisation; graph theory; network topology; analog network; circuit implementation; combinatorial optimization problems; graph theory; physical limitations; shortest path problem; simulation results; steady-state solutions; variable turn-on-voltage diodes; Circuit simulation; Concurrent computing; Diodes; Energy consumption; Hardware; Large-scale systems; Neural networks; Optimization methods; Shortest path problem; Steady-state;
fLanguage :
English
Journal_Title :
Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on
Publisher :
ieee
ISSN :
1057-7122
Type :
jour
DOI :
10.1109/81.802826
Filename :
802826
Link To Document :
بازگشت