Characterizing matchings as the intersection of matroids |
| |
Authors: | Email author" target="_blank">Sándor P?FeketeEmail author Robert T?Firla Bianca?Spille |
| |
Institution: | (1) Abteilung für Mathematische Optimierung, TU Braunschweig, Pockelsstr.14, 38106 Braunschweig, Germany;(2) Institut für Mathematische Optimierung, Otto-von-Guericke-Universität Magdeburg, Universitätsplatz 2, 39106 Magdeburg, Germany |
| |
Abstract: | This paper deals with the problem of representing the matching independence system in a graph as the intersection of finitely many matroids. After characterizing the graphs for which the matching independence system is the intersection of two matroids, we study the function (G), which is the minimum number of matroids that need to be intersected in order to obtain the set of matchings on a graph G, and examine the maximal value, (n), for graphs with n vertices. We describe an integer programming formulation for deciding whether (G) k. Using combinatorial arguments, we prove that (n)![isin](/content/bx4e9qhyr1e6epgw/xxlarge8712.gif) (log logn). On the other hand, we establish that (n) O(logn/ log logn). Finally, we prove that (n)=4 for n=5, ,12, and sketch a proof of (n)=5 for n=13,14,15.An earlier version appears as an extended abstract in the Proceedings of COMB 01 5]. Supported by the Gerhard-Hess-Forschungs-Förderpreis (WE 1462) of the German Science Foundation (DFG) awarded to R. Weismantel. |
| |
Keywords: | matching matroid intersection |
本文献已被 SpringerLink 等数据库收录! |
|