Abstract
In this paper we consider the problem of partitioning a graph into two parts of equal sizes with minimal sum of edge weights between them. It is known that this problem is NP-complete and can be reduced to the minimization of a quadratic binary functional with constraints. In previous work it was shown that raising the matrix of couplings to some power leads to a significant increase of the basin of attraction of the deepest functional minima. This means that such transformation possesses great optimizing abilities. In this paper we show that in spite of the constraints present in the graph bipartitioning problem, the proposed matrix transformation approach works very well with this problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Kernighan, B.W., Lin, S.: An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Tech. Journal 49, 291–307 (1970)
Hopfield, J.J.: Neural networks and physical systems with emergent collective computational abilities. Proc. Nat. Acad. Sci. USA 79, 2554–2558 (1982)
Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by Simulated Annealing. Science 220(4598), 671–680 (1983)
Karypis, G., Kumar, V.: A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM J. Sci. Comput. 20(1), 359–392 (1997)
Houdayer, J., Martin, O.C.: Hierarchical approach for computing spin glass ground states. Phys. Rev. E 64, 56704 (2001)
Karandashev, Y.M., Kryzhanovsky, B.V.: Transformation of Energy Landscape in the Problem of Binary Minimization. Doklady Mathematics 80(3), 927–931 (2009)
Karandashev, Y.M., Kryzhanovsky, B.V.: Binary Optimization: Efficient Increasing of Global Minimum Basin of Attraction. Opt. Memory & Neural Net (Information Optics) 19(2), 110–125 (2010)
Hartmann, A.K., Rieger, H. (eds.): Optimization Algorithms in Physics. Wiley-VCH, Berlin (2001)
Hartmann, A.K., Rieger, H. (eds.): New Optimization Algorithms in Physics. Wiley-VCH, Berlin (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Karandashev, I.M., Kryzhanovsky, B.V. (2011). Transformation of Edge Weights in a Graph Bipartitioning Problem. In: Honkela, T., Duch, W., Girolami, M., Kaski, S. (eds) Artificial Neural Networks and Machine Learning – ICANN 2011. ICANN 2011. Lecture Notes in Computer Science, vol 6792. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21738-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-21738-8_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21737-1
Online ISBN: 978-3-642-21738-8
eBook Packages: Computer ScienceComputer Science (R0)