Matroid matching and some applications |
| |
| Authors: | L Lovász |
| |
| Institution: | 1. Bolyai Institute, University of Szeged, Szeged, Hungary;2. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada |
| |
| Abstract: | The polymatroid matching problem, also known as the matchoid problem or the matroid parity problem, is polynomially unsolvable in general but solvable for linear matroids. The solution for linear matroids is analysed and results concerning arbitrary matroids are given from which the linear case follows immediately. The same general result is then applied to find a maximum circuitfree partial hypergraph of a 3-uniform hypergraph, to generalize a theorem of Mader on packing openly disjoint paths starting and ending in a given set, and to study a problem in structural rigidity. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
