Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652791 | Electronic Notes in Discrete Mathematics | 2010 | 8 Pages |
Abstract
In this paper, we investigate heuristics for approximate graph matching, in particular its formulation as a Maximum Common Edge Subgraph problem. Our experiments suggest that a small percentage of accurate node matches is sufficient to get near optimal solutions using a simple hill-climbing. The real challenge could then be to somehow drag the search in this zone. For this purpose, we discuss the use of similarity measures. We present and assess the performance of two similarity measures. Very good results were obtained on labeled graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics