A linear programming approach for the weighted graph matchingproblem
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...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , |
| التنسيق: | article |
| منشور في: |
1993
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | https://eprints.kfupm.edu.sa/id/eprint/14224/1/14224_1.pdf https://eprints.kfupm.edu.sa/id/eprint/14224/2/14224_2.doc |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513384062386176 |
|---|---|
| author | Almohamad, H.A. |
| author2 | Duffuaa, S.O. unknown |
| author2_role | author author |
| author_facet | Almohamad, H.A. Duffuaa, S.O. unknown |
| author_role | author |
| dc.creator.none.fl_str_mv | Almohamad, H.A. Duffuaa, S.O. unknown |
| dc.date.none.fl_str_mv | 1993-05 2020 |
| dc.format.none.fl_str_mv | application/pdf application/msword |
| dc.identifier.none.fl_str_mv | https://eprints.kfupm.edu.sa/id/eprint/14224/1/14224_1.pdf https://eprints.kfupm.edu.sa/id/eprint/14224/2/14224_2.doc (1993) A linear programming approach for the weighted graph matchingproblem. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 15. |
| dc.language.none.fl_str_mv | en en |
| dc.publisher.none.fl_str_mv | IEEE |
| dc.relation.none.fl_str_mv | https://eprints.kfupm.edu.sa/id/eprint/14224/ |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Computer |
| dc.title.none.fl_str_mv | A linear programming approach for the weighted graph matchingproblem |
| 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(n 6L) 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 |
| eu_rights_str_mv | openAccess |
| format | article |
| id | KFUPM_3dbddfadd90fb3eb9dfcef045596aeef |
| identifier_str_mv | (1993) A linear programming approach for the weighted graph matchingproblem. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 15. |
| language_invalid_str_mv | en |
| network_acronym_str | KFUPM |
| network_name_str | King Fahd University of Petroleum and Minerals |
| oai_identifier_str | oai::14224 |
| publishDate | 1993 |
| publisher.none.fl_str_mv | IEEE |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | A linear programming approach for the weighted graph matchingproblemAlmohamad, H.A.Duffuaa, S.O.unknownComputerA 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(n 6L) 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 methodsIEEE1993-052020ArticlePeerReviewedinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/articleapplication/pdfapplication/mswordhttps://eprints.kfupm.edu.sa/id/eprint/14224/1/14224_1.pdfhttps://eprints.kfupm.edu.sa/id/eprint/14224/2/14224_2.doc (1993) A linear programming approach for the weighted graph matchingproblem. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 15. enenhttps://eprints.kfupm.edu.sa/id/eprint/14224/info:eu-repo/semantics/openAccessoai::142242019-11-01T14:04:48Z |
| spellingShingle | A linear programming approach for the weighted graph matchingproblem Almohamad, H.A. Computer |
| status_str | publishedVersion |
| title | A linear programming approach for the weighted graph matchingproblem |
| title_full | A linear programming approach for the weighted graph matchingproblem |
| title_fullStr | A linear programming approach for the weighted graph matchingproblem |
| title_full_unstemmed | A linear programming approach for the weighted graph matchingproblem |
| title_short | A linear programming approach for the weighted graph matchingproblem |
| title_sort | A linear programming approach for the weighted graph matchingproblem |
| topic | Computer |
| url | https://eprints.kfupm.edu.sa/id/eprint/14224/1/14224_1.pdf https://eprints.kfupm.edu.sa/id/eprint/14224/2/14224_2.doc |