A Multiply Constrained Matroid Optimization Problem
Leclerc, Matthias and Rendl, Franz
(1989)
A Multiply Constrained Matroid Optimization Problem.
Published in:
Discrete mathematics Vol. 73 (1-2).
pp. 207-212.
Abstract
We consider the problem of finding a minimum weight basis of a matroid satisfying additional conditions which can be described as follows: each element of the matroid is assigned a color and feasible bases can use at most a prescribed number of elements from each color. This problem is a special case of weighted matroid intersection. We provide an algorithm for this problem which improves general matroid intersection algorithms by exploiting the simple structure of the side constraints.
Actions:
Content information:
Deposit Information:
ZAIK Number: | zpr87-040 |
---|---|
Depositing User: | Archive Admin |
Date Deposited: | 02 Apr 2001 00:00 |
Last Modified: | 19 Jan 2012 12:28 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/40 |