IIIT Hyderabad Publications |
|||||||||
|
Optimization of Quadratic Forms: Unified Minimum/Maximum Cut Computation in Directed/Undirected GraphsAuthors: Garimella Ramamurthy Date: 2015-11-10 Report no: IIIT/TR/2015/62 AbstractIn this research paper, the problem of optimization of a quadratic form over the corners of hypercube is reviewed. Results related to the computation of global optimum stable / anti-stable state of a Hopfield Neural Network (HNN) are discussed. Using these results, an efficient algorithm for computation of minimum cut as well as maximum cut in an undirected as well as directed graph is discussed. Also, POTENTIALLY, a deterministic exact polynomial time algorithm for the NP-Hard problem of maximum cut in an undirected graph is discussed. Effectively, unified approach to minimum cut as well as maximum cut computation in arbitrary directed as well as undirected graphs is presented. Full report: pdf Centre for Security, Theory and Algorithms |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |