A perfect matching algorithm for sparse bipartite graphs (Q759771)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A perfect matching algorithm for sparse bipartite graphs |
scientific article; zbMATH DE number 3882482
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A perfect matching algorithm for sparse bipartite graphs |
scientific article; zbMATH DE number 3882482 |
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
0.841637909412384
0 references
0.8157210350036621
0 references
