Name
Abstract | ||
|---|---|---|
The graph edit distance (GED) is a widely used distance measure for attributed graphs. It has recently been shown that the problem of computing GED, which is a NP-hard optimization problem, can be formulated as a quadratic assignment problem (QAP). This formulation is useful, since it allows to derive well performing approximative heuristics for GED from existing techniques for QAP. In this paper, we focus on the case where the edit costs that underlie GED are quasimetric. This is the case in many applications of GED. We show that, for quasimetric edit costs, it is possible to reduce the size of the corresponding QAP formulation. An empirical evaluation shows that this reduction significantly speeds up the QAP-based approximative heuristics for GED. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/ICPR.2018.8546055 | 2018 24TH INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION (ICPR) |
Field | DocType | ISSN |
Graph,Pattern recognition,Quadratic assignment problem,Computer science,Upper and lower bounds,Cascading Style Sheets,Theoretical computer science,Heuristics,Artificial intelligence,Optimization problem,Graph edit distance | Conference | 1051-4651 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Blumenthal | 1 | 24 | 6.26 |
| Évariste Daller | 2 | 0 | 0.68 |
| Sébastien Bougleux | 3 | 395 | 27.05 |
| L. Brun | 4 | 58 | 5.51 |
| Johann Gamper | 5 | 465 | 54.06 |