Portal de Periódicos da CAPES

An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

1973; Society for Industrial and Applied Mathematics; Volume: 2; Issue: 4 Linguagem: Inglês

10.1137/0202019

1095-7111

John E. Hopcroft, Richard M. Karp,

graph theory and CDMA systems

The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to $(m + n)\sqrt n $.Keywordsalgorithmalgorithmic analysisbipartite graphscomputational complexitygraphsmatching