计算机科学
匹配(统计)
图形
Blossom算法
理论计算机科学
算法
功率图分析
计算复杂性理论
数学
统计
作者
Luigi P. Cordella,Pasquale Foggia,Carlo Sansone,Mario Vento
标识
DOI:10.1109/iciap.1999.797762
摘要
The paper discusses the performance of a graph matching algorithm tailored for dealing with large graphs in computer vision without using information about the topology of the graphs to be matched. The algorithm, presented in more detail in other papers (and publicly available on the WWW as VF), is now discussed with reference to its computational complexity and memory requirements. The performance analysis is carried out by theoretically characterizing the matching time and the required memory in the best and worst cases. The theoretical analysis is completed by tests on a database of graphs randomly generated. The algorithm is compared with the one proposed by Ullmann (1976): experimental results confirmed the theoretical expectations, highlighting the overall efficiency of the algorithm. Some results obtained by researchers who recently used the algorithm in application domains requiring a massive use of graph matching techniques are finally reported.
科研通智能强力驱动
Strongly Powered by AbleSci AI