Record Details


Field	Value

Title	Application of DC analyzer to combinatorial optimization problems

Names	TRIVEDI, GAURAV PUNGLIA, SUMIT NARAYANAN, H
Date Issued	2007 (iso8601)
Abstract	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.
Genre	Article
Topic	Circuit Optimisation
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

ICAR Research Data Repository for Knowledge Management