A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM
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 L1 norm and then transforming the resulting quadratic optimization problem to a linear one. The linear program is solved using a Simplex-b...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | article |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://eprints.kfupm.edu.sa/id/eprint/1985/1/a_linear_programming_approach_for_the_we_almohamad_isi_a1993lb47000012.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513400894128128 |
|---|---|
| author | Al-Mohamad, HA |
| author2 | Duffuaa, S. O. unknown |
| author2_role | author author |
| author_facet | Al-Mohamad, HA Duffuaa, S. O. unknown |
| author_role | author |
| dc.creator.none.fl_str_mv | Al-Mohamad, HA Duffuaa, S. O. unknown |
| dc.date.*.fl_str_mv | 2020 |
| dc.format.none.fl_str_mv | application/pdf |
| dc.identifier.none.fl_str_mv | https://eprints.kfupm.edu.sa/id/eprint/1985/1/a_linear_programming_approach_for_the_we_almohamad_isi_a1993lb47000012.pdf A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 15. pp. 522-525. |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | IEEE COMPUTER SOC |
| dc.relation.none.fl_str_mv | https://eprints.kfupm.edu.sa/id/eprint/1985/ http://isi.kfupm.edu.sa/journals/pdf/A/a_linear_programming_approach_for_the_we_almohamad_isi_a1993lb47000012.pdf |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Systems |
| dc.title.none.fl_str_mv | A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM |
| dc.type.none.fl_str_mv | Article PeerReviewed info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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 L1 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(n6 L) for matching graphs of size n. The developed algorithm is compared to two other algorithms. One is based on an eigen decomposition 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | KFUPM_f4fcc566b24b1131c9d853604697753d |
| identifier_str_mv | A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 15. pp. 522-525. |
| language_invalid_str_mv | en |
| network_acronym_str | KFUPM |
| network_name_str | King Fahd University of Petroleum and Minerals |
| oai_identifier_str | oai::1985 |
| publishDate | 2020 |
| publisher.none.fl_str_mv | IEEE COMPUTER SOC |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEMAl-Mohamad, HADuffuaa, S. O.unknownSystemsA linear programming (LP) approach is proposed for the weighted graph matching problem. A linear program is obtained by formulating the graph matching problem in L1 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(n6 L) for matching graphs of size n. The developed algorithm is compared to two other algorithms. One is based on an eigen decomposition 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.IEEE COMPUTER SOCArticlePeerReviewedinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/articleapplication/pdfhttps://eprints.kfupm.edu.sa/id/eprint/1985/1/a_linear_programming_approach_for_the_we_almohamad_isi_a1993lb47000012.pdf A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 15. pp. 522-525. enhttps://eprints.kfupm.edu.sa/id/eprint/1985/http://isi.kfupm.edu.sa/journals/pdf/A/a_linear_programming_approach_for_the_we_almohamad_isi_a1993lb47000012.pdf2020info:eu-repo/semantics/openAccessoai::19852019-11-01T13:30:05Z |
| spellingShingle | A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM Al-Mohamad, HA Systems |
| status_str | publishedVersion |
| title | A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM |
| title_full | A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM |
| title_fullStr | A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM |
| title_full_unstemmed | A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM |
| title_short | A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM |
| title_sort | A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM |
| topic | Systems |
| url | https://eprints.kfupm.edu.sa/id/eprint/1985/1/a_linear_programming_approach_for_the_we_almohamad_isi_a1993lb47000012.pdf |