Faster scaling algorithms for general graph matching problems

1991/10/01 by Harold N. Gabow, Robert E. Tarjan · 3 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Advanced Graph Theory Research #Citation #Computer science #Graph #Matching (statistics) #Algorithm #Scaling #Theoretical computer science #Mathematics #World Wide Web #Statistics

paper · pdf · doi:10.1145/115234.115366

openalex publication_date 1991/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22

Abstract

An algorithm for minimum-cost matching on a general graph with integral edge costs is

Citations

• Data Structures and Network Algorithms
• Applications of Path Compression on Balanced Trees
• A linear-time algorithm for a special case of disjoint set union
• Combinatorial optimization: networks and matroids
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs
• Paths, Trees, and Flowers

Cited by

• The Weighted Matching Approach to Maximum Cardinality Matching
• Node-balancing by edge-increments
• Hopcroft–Karp algorithm [wikipedia]