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.


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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
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