A Lagrangian Relaxation Network for Graph Matching  

Oleh:

Rangarajan, A. ; Mjolsness, E. D.

Jenis: Article from Journal - ilmiah internasional
Dalam koleksi: IEEE Transactions on Neural Networks vol. 7 no. 6 (1996), page 1365-1381.
Topik: networks; lagrangian relaxation; network; graph matching

Ketersediaan

Perpustakaan Pusat (Semanggi) Nomor Panggil: II36.1 Non-tandon: 1 (dapat dipinjam: 0) Tandon: tidak ada

Lihat Detail Induk

Isi artikel

A Lagrangian relaxation network for graph matching is presented. The problem is formulated as follows : given graphs G and g, find a permutation matrix M that brings the two sets of vertices into correspondence. Permutation matrix constraints are formulated in the framework of deterministic annealing. Our approach is in the same spirit as a Lagrangian decomposition approach in that the row and column constraints are satisfied separately with a Lagrange multiplier used to equate the two “solutions”. Due to the unavoidable symmetries in graph isomorphism (resulting in multiple global minima), we add a symmetry - breaking self - amplification term in order to obtain a permutation matrix. With the application of a fixpoint preserving algebraic transformation to both the distance measure and self - amplification terms, we obtain a Lagrangian relaxation network. The network performs minimization with respect to the Lagrange parameters and maximization with respect to the permutation matrix variables. Simulation results are shown on 100 node random graphs and for a wide range of connectivities.

Opini Anda

Klik untuk menuliskan opini Anda tentang koleksi ini!

Kembali