文献

J-GLOBAL ID：201802276782441024   整理番号：18A0384892

Hausdorffマッチングと欲張り割当を組み合わせたグラフ編集距離の改良された二次時間近似【Powered by NICT】

Improved quadratic time approximation of graph edit distance by combining Hausdorff matching and greedy assignment

著者 (5件)： Fischer Andreas (Department of Informatics, University of Fribourg, Boulevard de Perolles 90, Fribourg 1700, Switzerland) ,  Fischer Andreas (Institute of Complex Systems, University of Applied Sciences and Arts Western Switzerland, Boulevard de Perolles 80, Fribourg 1700, Switzerland) ,  Riesen Kaspar (Institute for Information Systems, University of Applied Sciences and Arts Northwestern Switzerland, Riggenbachstrasse 16, Olten 4600, Switzerland) ,  Riesen Kaspar (Institute of Computer Science and Applied Mathematics, University of Bern, Neubrueckstrasse 10, Bern 3012, Switzerland) ,  Bunke Horst (Institute of Computer Science and Applied Mathematics, University of Bern, Neubrueckstrasse 10, Bern 3012, Switzerland)
資料名： Pattern Recognition Letters  (Pattern Recognition Letters)
巻： 87  ページ： 55-62  発行年： 2017年 
JST資料番号： H0913A  ISSN： 0167-8655  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 多項式時間でのグラフ編集距離の近似は構造的パターン認識のための大規模任意標識グラフを比較することが可能になった。最近の近似フレームワークでは,二部グラフマッチング(BP)は,編集距離の問題を減少させる局所部分構造物の間の立方晶時間線形和割当問題(LSAP)に提案されている。研究の同一ラインに続いて,二次時間近似に向けた最初の試みは最近,Hausdorffマッチング(Hausdorff編集距離)と欲張り割当(欲張り編集距離)に基づく上限に基づく下限を検討した。本論文では,二つの方法を比較し,両者の利点を結合した新しい上限(BP2)を導出した。IAMグラフデータベースリポジトリに実験的評価では,提案した二次時間法は,または,全く驚くべきこと同様に,立方晶時間法よりも優れたいくつかのケースでことを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 構造物 ,  線形性 ,  *グラフ ,  *近似法 ,  *マッチング ,  CASE ,  割当問題 ,  パターン認識 ,  立方晶系
準シソーラス用語： グラフマッチング ,  多項式時間 ,  *編集距離 , 【Automatic Indexing@JST】

著者キーワード (4件)： グラフマッチング ,  グラフは編集距離 ,  グラフ編集距離の近似 ,  H ausdorff距離

分類 (1件)： パターン認識  (JE07000S)

タイトルに関連する用語 (5件)： マッチング ,  割当 ,  グラフ ,  編集距離 ,  近似