VFグラフマッチングアルゴリズムの性能評価

本論文では、コンピュータビジョンにおける大規模グラフを扱うために特化したグラフマッチングアルゴリズムの性能について論じます。マッチング対象のグラフのトポロジーに関する情報を使用することなく、アルゴリズムは他の論文でより詳しく説明されており（VFとしてWWWで公開されています）、その計算複雑度とメモリ要件に言及しています。性能分析は、最良および最悪の場合におけるマッチング時間と必要なメモリを理論的に特性化することによって行われます。理論的分析は、ランダムに生成されたグラフのデータベースに対するテストによって行われます。アルゴリズムはUllmann（1976）によって提案されたものと比較され、実験結果は理論的な期待を確認し、アルゴリズムの全体的な効率を強調しました。グラフマッチング技術の大量使用を必要とする応用分野で最近アルゴリズムを使用した研究者によって得られた結果も報告されます。