Brick decompositions and the matching rank of graphs Export

@article{citeulike:1847722, abstract = {Abstract\ \ The number of linearly independent perfect matchings of a graph — or, equivalently, the dimension of the perfect matching polytope — is determined in various senses. First it is shown that the fact that every linear objective function can be optimized over the perfect matchings in polynomial time implies the existence of a polynomial-time algorithm to determine the dimension of this set. This observation also yields polynomial algorithms to determine, among others, the number of linearly independent common bases of two matroids and the number of linearly independent maximum stable sets in claw-free or perfect graphs. For the case of perfect matchings, Naddef's minimax theorem for the dimension of the perfect matching polytope is strengthened and it is shown how the decomposition theory of matchings in graphs can be applied to derive a particularly simple formula for this dimension. This formula is based upon the number of constituents of a certain decomposition of the graph which we call a brick decomposition. Finally, these results are applied to obtain a description of the facets of the perfect matching polytope.}, author = {Edmonds, J. and Pulleyblank, W. and Lov\'{a}sz, L.}, citeulike-article-id = {1847722}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/BF02579233}, day = {23}, doi = {10.1007/BF02579233}, journal = {Combinatorica}, keywords = {matching}, number = {3}, pages = {247--274}, posted-at = {2007-10-31 16:11:12}, priority = {2}, title = {Brick decompositions and the matching rank of graphs}, url = {http://dx.doi.org/10.1007/BF02579233}, volume = {2}, year = {1982} }

TY - JOUR ID - citeulike:1847722 L3 - citeulike-article-id:1847722 N2 - Abstract  The number of linearly independent perfect matchings of a graph — or, equivalently, the dimension of the perfect matching polytope — is determined in various senses. First it is shown that the fact that every linear objective function can be optimized over the perfect matchings in polynomial time implies the existence of a polynomial-time algorithm to determine the dimension of this set. This observation also yields polynomial algorithms to determine, among others, the number of linearly independent common bases of two matroids and the number of linearly independent maximum stable sets in claw-free or perfect graphs. For the case of perfect matchings, Naddef’s minimax theorem for the dimension of the perfect matching polytope is strengthened and it is shown how the decomposition theory of matchings in graphs can be applied to derive a particularly simple formula for this dimension. This formula is based upon the number of constituents of a certain decomposition of the graph which we call a brick decomposition. Finally, these results are applied to obtain a description of the facets of the perfect matching polytope. IS - 3 JF - Combinatorica EP - 274 TI - Brick decompositions and the matching rank of graphs VL - 2 SP - 247 KW - matching AU - Edmonds, J AU - Pulleyblank, W AU - Lovász, L PY - 1982//23/ UR - http://dx.doi.org/10.1007/BF02579233 ER -