A perfect matching algorithm for sparse bipartite graphs (Q759771): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Technical Note—An Improved Algorithm for the Bottleneck Assignment Problem / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Depth-First Search and Linear Graph Algorithms / rank | |||
Normal rank | |||
Latest revision as of 16:23, 14 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A perfect matching algorithm for sparse bipartite graphs |
scientific article |
Statements
A perfect matching algorithm for sparse bipartite graphs (English)
0 references
1984
0 references
The algorithms for finding a perfect matching, if any, in a bipartite undirected graph G usually start with a matching (which may not be maximum) and construct, if it exists, a matching of greater cardinality by determining augmenting paths. This is generally obtained through an associated directed graph \(\bar G.\) The paper shows that those edges of \(\bar G\) which link vertices belonging to different strongly connected components should not be included in augmenting paths. An application to the block triangularization of very large, sparse, nonsingular matrices is given.
0 references
block triangularization of matrices
0 references
algorithms
0 references
perfect matching
0 references
