An algebraic matching algorithm
type: Item
instance of: scholarly article
title: An algebraic matching algorithm
zbMATH Open document ID: 0949.05062
author: James F. Geelen
published in: Combinatorica
publication date: 2000-11-13T00:00:00Z
review text: The Tutte matrix of an undirected simple graph \(G=(V, E)\) is the skew-symmetric matrix \(T=(t_{ij})\) with \(t_{ij}=z_e\) or \(-z_e\), when \(\{i,j\}=e\in E\), and \(t_{ij}=0\) when \(\{i,j\}\notin E\), with \(\{z_e\mid e\in E\}\) a set of algebraic independent commuting indeterminates. The rank of the Tutte matrix is precisely twice the size of a maximum matching in \(G\), and hence, \(G\) has a perfect matching, if and only if \(T\) is non-singular. This paper addresses the question to use this result to obtain an efficient algorithm for solving the maximum matching problem on graphs. It is shown that one can find a constant value from \(\{1,\dots, n\}\) \((n=|V|)\) for each indeterminant, such that the rank of this `evaluation' of \(T\) equals the rank of \(T\). Hence, this gives an algorithm to compute (the size of) a maximum matching of \(G\): first find this evaluation, and then compute its rank. This gives a new technique to algorithmically solve the maximum matching problem. The algorithm uses polynomial time, but significantly more than Edmonds' augmenting path algorithm.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1528608
zbMATH Keywords: matching
zbMATH Keywords: Tutte matrix
reviewed by: Hans L. Bodlaender
MaRDI profile type: Publication
full work available at URL: s004930070031
OpenAlex ID: W1989949821
DOI: 10.1007/S004930070031
description: scientific article; zbMATH DE number 1528608