Approximation of graph edit distance in quadratic time

DOI10.1007/978-3-319-18224-7_1MaRDI QIDQ3300141zbMATH OpenOpenAlexFDO

Authors Kaspar Riesen, M. Ferrer, Andreas Fischer, Horst Bunke

Publication date 27 July 2020

Published in Graph-Based Representations in Pattern Recognition (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-18224-7_1

zbMATH Keywords

assignment costcost matrixgreedy algorithmgreedy approachquadratic time

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Speeding up graph edit distance computation through fast bipartite matching
• Approximation of graph edit distance based on Hausdorff matching
• A survey of graph edit distance
• Bipartite Graph Matching for Computing the Edit Distance of Graphs
• Structural pattern recognition with graph edit distance. Approximation algorithms and applications

Cites work

• A distance measure between attributed relational graphs for pattern recognition
• A survey of graph edit distance
• Algorithms for the Assignment and Transportation Problems
• Assignment Problems
• Graph-Based Representations in Pattern Recognition
• Inexact graph matching for structural pattern recognition

Cited in

(14)

• Approximation of graph edit distance based on Hausdorff matching
• EmbAssi: embedding assignment costs for similarity search in large graph databases
• Graph simplification and matching using commute times
• Speeding up graph edit distance computation through fast bipartite matching
• On the influence of node centralities on graph edit distance for graph classification
• scientific article; zbMATH DE number 2090203 (Why is no real title available?)
• A novel software toolkit for graph edit distance computation
• Exact computation of graph edit distance for uniform and non-uniform metric edit costs
• Improved Graph Edit Distance Approximation with Simulated Annealing
• Structural pattern recognition with graph edit distance. Approximation algorithms and applications
• A Quadratic Programming Approach to the Graph Edit Distance Problem
• Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching
• A survey of graph edit distance
• Image categorization: Graph edit distance \(+\) edge direction histogram

This page was built for publication: Approximation of graph edit distance in quadratic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3300141)