A linear programming approach for the weighted graph matching problem

IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 1 May 1993

H.A. Al-Mohamad, Salih O. Duffuaa

DOI10.1109/34.211474

Source URL

Citations236

SJR quartileQ1

SJR score3.91

SNIP5.99

TL;DR

Experimental results showed that the LP approach is superior in matching graphs than both other methods.

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/sub 1/ 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/sup 6/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

Computer Science

Mathematics in Science and Engineering/Mathematics in science and engineeringFuzzy Sets and Systems - Theory and Applications

6,430 Citations1980Didier Dubois, Henri Prade

Journal of the Operational Research SocietyLinear Programming and Network Flows

1,880 Citations1978C. R. Sergeant, Mokhtar S. Bazaraa +1 more

IEEE Transactions on Pattern Analysis and Machine IntelligenceAn eigendecomposition approach to weighted graph matching problems

718 Citations1988Shinji Umeyama

An approximate solution to the weighted-graph-matching problem is discussed for both undirected and directed graphs and an analytic approach is used instead of a combinatorial or iterative approach to the optimum matching problem.

European Journal of Operational ResearchLinear programming and network flows

674 Citations1991Dirk Cattrysse

IEEE Transactions on Systems Man and CyberneticsError-Correcting Isomorphisms of Attributed Relational Graphs for Pattern Analysis

325 Citations1979Wen‐Hsiang Tsai, King‐Sun Fu

The pattern deformational model proposed by Tsai and Fu is extended so that numerical attributes and probability or density distributions can be introduced into primitives and relations in a nonhierarchical relational graph.

European Journal of Operational ResearchCombinatorial optimization algorithm and complexity

103 Citations1983Antoon Kolen

Discrete Relaxation for Matching Relational Structures

46 Citations1978Les Kitchen

Local constraint analysis ('discrete relaxation') is used to reduce ambiguity in matching pairs of relational structures if the set of possible local properties is sufficiently large, this generally results in unambiguous identifications after only a few iterations.

Relaxation Applied to Matching Quantitative Relational Structures

44 Citations1978Les Kitchen

The method is empirically shown to be very sensitive to the exact form of the updating rule used, but with the proper updating rule, the method works well, and is remarkably tolerant of measurement errors.

NanoscaleAn algorithm for solving linear programming programs in O(n3L) operations

34 Citations1988Clóvis C. Gonzaga

Applied Mathematical ModellingA polynomial transform for matching pairs of weighted graphs

24 Citations1991H.A. Al-Mohamad

Fundamental symmetric polynomials are used for matching pairs of directed and undirected weighted graphs and it is shown that the complexity of the present algorithm is of O(n 3 ).