A n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs
Explore this paper's citation graph
Summary
This 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)√ n .
- Type
- article
- Published
- 1971-10-13
- Cited by
- 3,130
- References
- 4
- OpenAlex
- https://openalex.org/W2536967169
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:16337582
Keywords
Bipartite graph, Computer science, Algorithm, Combinatorics, Mathematics
References
Cited by
- Quantum complexity of graph and algebraic problems
- On semantic issues connected with incomplete information data bases (abstract)
- Similarity-Based Ontology Alignment in OWL-Lite
- The NP-completeness of Completing Partial anti-symmetric Latin squares
- Graph Colouring with Input Restrictions
- A C++ implementation of a polynomial time approximation scheme for aligning protein structures.
- Scalable algorithms for communication networks
- Reasoning in the Description Logic EL Extended with an n-ary Existential Quantifier
- An interactive design and fault location tool for electronic circuits
- A class of multicriterial problems on graphs and hypergraphs
- Handbook of Constraint Programming
- Sobre subclases y variantes de los grafos perfectos
- Classical and Quantum Algorithms for Finding Cycles
- Skew Minimization Problem with Possible Sink Displacement
- An Algorithm for the Validation of Executable Completions of an Abstract BPEL Process
- Filtrage basé sur des contraintes "tous différents" pour l'isomorphisme de sous-graphes
- Fast Switched Backplane for a Gigabit Switched Router
- A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in General Graphs
- On packet switch design
- Routing and Sorting on Fixed Topologies
Related papers
- DETERMINING QUALITY REQUIREMENTS AT THE UNIVERSITIES TO IMPROVE THE QUALITY OF EDUCATION
- 2-Bipartite Matching Extendability of C_n×P_2
- Overlapping Community Detecting Based on Complete Bipartite Graphs in Micro-Bipartite Network Bi-Egonet
- A New Modularity for Detecting One-to-Many Correspondence of Communities in Bipartite Networks
- Primärzerlegung in Steinschen Algebren
- Über unirationale Scharen auf algebraischen Mannigfaltigkeiten
- Bipartite Independent Number and Hamilton-Biconnectedness of Bipartite Graphs
- Coloring Graphs With Forbidden Almost Bipartite Subgraphs
- On a bipartition problem of Bollobás and Scott