A linear programming approach for the weighted graph matching problem

Author

Almohamad, H.A. ; Duffuaa, S.O.

Author_Institution

Dept. of Syst. Eng., King Fahd Univ. of Pet. & Miner., Dhahran, Saudi Arabia

Volume

15

Issue

5

fYear

1993

fDate

5/1/1993 12:00:00 AM

Firstpage

522

Lastpage

525

Abstract

A linear programming (LP) approach is proposed for the weighted graph matching problem. A linear program is obtained by formulating the graph matching problem in L₁ norm and then transforming the resulting quadratic optimization problem to a linear one. The linear program is solved using a simplex-based algorithm. Then, approximate 0-1 integer solutions are obtained by applying the Hungarian method on the real solutions of the linear program. The complexity of the proposed algorithm is polynomial time, and it is O(n ⁶L) for matching graphs of size n. The developed algorithm is compared to two other algorithms. One is based on an eigendecomposition approach and the other on a symmetric polynomial transform. Experimental results showed that the LP approach is superior in matching graphs than both other methods

Keywords

computational complexity; linear programming; pattern recognition; Hungarian method; computational complexity; eigendecomposition; linear programming; polynomial time; quadratic optimization; simplex-based algorithm; symmetric polynomial transform; weighted graph matching; Euclidean distance; Linear programming; Optimization methods; Pattern matching; Pattern recognition; Polynomials; Relaxation methods; Symmetric matrices; Systems engineering and theory; Tree graphs;

fLanguage

English

Journal_Title

Pattern Analysis and Machine Intelligence, IEEE Transactions on

Publisher

ieee

ISSN

0162-8828

Type

jour

DOI

10.1109/34.211474

Filename

211474