Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching

DOI10.1016/J.INS.2022.03.017MaRDI QIDQ6199741zbMATH OpenOpenAlexWikidataFDO

Authors David B. Blumenthal, Sébastien Bougleux, Anton Dignös, Johann Gamper

Publication date 28 February 2024

Published in Information Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.ins.2022.03.017

zbMATH Keywords

dynamic programminggraph edit distancebipartite matchingdata matchingenumeration with dissimilarity

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) General topics of discrete mathematics in relation to computer science (68R01)

Recommendations

• Finding all minimum-cost perfect matchings in Bipartite graphs
• An efficient algorithm for the bipartite matching problem
• scientific article; zbMATH DE number 1104328
• scientific article; zbMATH DE number 2081005
• Optimum matchings in weighted bipartite graphs

Cites work

• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 1104328 (Why is no real title available?)
• scientific article; zbMATH DE number 2081005 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• A strong-connectivity algorithm and its applications in data flow analysis
• Algorithms for the Assignment and Transportation Problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Approximation of graph edit distance in quadratic time
• Depth-First Search and Linear Graph Algorithms
• Finding all minimum-cost perfect matchings in Bipartite graphs
• Finding all the perfect matchings in bipartite graphs
• Hamilton Paths in Grid Graphs
• Inexact graph matching for structural pattern recognition
• MDSM: microarray database schema matching using the Hungarian method
• The auction algorithm: A distributed relaxation method for the assignment problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

This page was built for publication: Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching

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