Fast linear sum assignment with error-correction and no cost constraints

被引：11

作者：

Bougleux, Sebastien ^{[1
]}

Gauzere, Benoit ^{[2
]}

Blumenthal, David B. ^{[3
]}

Brun, Luc ^{[1
]}

机构：

[1] Normandie Univ, UNICAEN, ENSICAEN, CNRS,GREYC,UMR 6072, F-14000 Caen, France

[2] Normandie Univ, UNIROUEN, UNIHAVRE, INSA Rouen,LITIS, F-76000 Rouen, France

[3] Free Univ Bozen Bolzano, Fac Comp Sci, Dominikanerpl 3, I-39100 Bolzano, Italy

来源：

PATTERN RECOGNITION LETTERS | 2020年 / 134卷

关键词：

Inexact graph matching; Linear assignment; Graph edit distance; GRAPH EDIT DISTANCE; COMPUTATION; ALGORITHM; SEARCH;

D O I：

10.1016/j.patrec.2018.03.032

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We propose an algorithm that efficiently solves the linear sum assignment problem with error-correction and no cost constraints. This problem is encountered for instance in the approximation of the graph edit distance. The fastest currently available solvers for the linear sum assignment problem require the pair-wise costs to respect the triangle inequality. Our algorithm is as fast as these algorithms, but manages to drop the cost constraint. The main technical ingredient of our algorithm is a cost-dependent factorization of the node substitutions. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：37 / 45

页数：9

共 32 条

[1] Graph edit distance contest: Results and future challenges [J].

Abu-Aisheh, Zeina ;

Gauzere, Benoit ;

Bougleux, Sebastien ;

Ramel, Jean-Yves ;

Brun, Luc ;

Raveaux, Romain ;

Heroux, Pierre ;

Adam, Sebastien .

PATTERN RECOGNITION LETTERS, 2017, 100 :96-103

[2]

[Anonymous], 1956, Nav. Res. Logist. Q., DOI [10.1002/nav.3800030404, DOI 10.1002/NAV.3800030404]

[3]

[Anonymous], 1976, Combinatorial Optimization: Networks and Matroids

[4] Improved Lower Bounds for Graph Edit Distance [J].

Blumenthal, David B. ;

Gamper, Johann .

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2018, 30 (03) :503-516

[5] Correcting and Speeding-Up Bounds for Non-Uniform Graph Edit Distance [J].

Blumenthal, David B. ;

Gamper, Johann .

2017 IEEE 33RD INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE 2017), 2017, :131-134

[6] A Hungarian Algorithm for Error-Correcting Graph Matching [J].

Bougleux, Sebastien ;

Gauzere, Benoit ;

Brun, Luc .

GRAPH-BASED REPRESENTATIONS IN PATTERN RECOGNITION (GBRPR 2017), 2017, 10310 :118-127

[7] Graph edit distance as a quadratic assignment problem [J].

Bougleux, Sebastien ;

Brun, Luc ;

Carletti, Vincenzo ;

Foggia, Pasquale ;

Gauzere, Benoit ;

Vento, Mario .

PATTERN RECOGNITION LETTERS, 2017, 87 :38-46

[8] EXTENSION OF MUNKRES ALGORITHM FOR ASSIGNMENT PROBLEM TO RECTANGULARMATRICES [J].

BOURGEOIS, F ;

LASSALLE, JC .

COMMUNICATIONS OF THE ACM, 1971, 14 (12) :802-+

[9] Inexact graph matching for structural pattern recognition [J].

Bunke, H. ;

Allermann, G. .

PATTERN RECOGNITION LETTERS, 1983, 1 (04) :245-253

[10]

Burkard R. E., 2009, Assignment problems, DOI DOI 10.1137/1.9780898717754

← 1 2 3 4 →