ISSN:
1439-6912
Keywords:
05C70
;
05B35
;
90C27
;
68Q25
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract We describe a common generalization of the weighted matching problem and the weighted matroid intersection problem. In this context we establish common generalizations of the main results on those two problems—polynomial-time solvability, min-max theorems, and totally dual integral polyhedral descriptions. New application of these results include a strongly polynomial separation algorithm for the convex hull of matchable sets of a graph, and a polynomial-time algorithm to compute the rank of a certain matrix of indeterminates.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01215915
Permalink