An Algebraic Matching Algorithm |
| |
Authors: | James F Geelen |
| |
Institution: | (1) Department of Combinatorics and Optimization, University of Waterloo; Waterloo, Ontario, Canada, N2L 3G1; E-mail: jfgeelen@math.uwaterloo.ca, CA |
| |
Abstract: | V by V skew-symmetric matrix , called the Tutte matrix, associated with a simple graph G=(V,E). He associates an indeterminate with each , then defines when , and otherwise. The rank of the Tutte matrix is exactly twice the size of a maximum matching of G. Using linear algebra and ideas from the Gallai–Edmonds decomposition, we describe a very simple yet efficient algorithm
that replaces the indeterminates with constants without losing rank. Hence, by computing the rank of the resulting matrix,
we can efficiently compute the size of a maximum matching of a graph.
Received September 4, 1997 |
| |
Keywords: | AMS Subject Classification (1991) Classes: 05C70 |
本文献已被 SpringerLink 等数据库收录! |
|