Record Details

Application of DC analyzer to combinatorial optimization problems

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Application of DC analyzer to combinatorial optimization problems
 
Creator TRIVEDI, GAURAV
PUNGLIA, SUMIT
NARAYANAN, H
 
Subject circuit optimisation
microprocessor chips
network analysis
random-access storage
 
Description Solution of many combinatorial optimization problems can be found by analyzing appropriate electrical networks made up of positive resistors, voltage sources, current sources and ideal diodes. This method is an alternative approach for the approximate solution of such problems. Two graph method based fast simulator is a more suitable option for this purpose than modified nodal analysis based conventional simulators. Using this approach the authors have made an attempt to solve min cost flow and single source shortest path problems. A planar min cost flow problem of size 200,000 nodes and 600,000 edges is solved by our simulator approximately within 0.1% of the optimum solution in about 11 mins. The authors have exactly solved a planar single source shortest path problem (having negative edge weights also) of size 100, 000 nodes and 600, 000 edges in about 2 mins. The authors have performed our experiments on a PIV processor having 1 GB RAM.
 
Publisher IEEE
 
Date 2008-12-19T10:49:22Z
2011-11-27T19:28:07Z
2011-12-15T09:56:16Z
2008-12-19T10:49:22Z
2011-11-27T19:28:07Z
2011-12-15T09:56:16Z
2007
 
Type Article
 
Identifier Proceedings of the 20th International Conference on VLSI Design held jointly with 6th International Conference on Embedded Systems, Bangalore, India, 6-10 January 2007, 869-874
0-7695-2762-0
10.1109/VLSID.2007.39
http://hdl.handle.net/10054/403
http://dspace.library.iitb.ac.in/xmlui/handle/10054/403
 
Language en