Eine Min-Max Beziehung für das Exakte Matroid Problem
Leclerc, Matthias
(1987)
Eine Min-Max Beziehung für das Exakte Matroid Problem.
Published in:
Archiv der Mathematik : ADM Vol. 49 (2).
pp. 103-105.
Abstract
Das Exakte Matroid-Problem ist: Gegeben sei ein Matroid M=(E,J), eine Teilmenge R von E und eine natürliche Zahl ell; finde eine Basis B von M, so dass vert Bcap Rvert =ell gilt. In der Arbeit wird eine Gleichung bewiesen, die das Maximum der R-Elemente in einer Basis in Beziehung zum Minimum der Summe der Ränge einer bestimmten Überdeckung von M setzt. Der Beweis beruht auf einer Charakterisierung des total dual ganzzahligen Systems für das Matroid-Polytop von Edmonds und Giles.
Actions:
Content information:
Item Type: | Article |
---|---|
Citations: | 0 (Google Scholar) | |
Uncontrolled Keywords: | exact matroid problem matroid polytope of Edmonds and Giles total dual integral system |
Subjects: |
|
Divisions: | Mathematical Institute |
Related URLs: |
Deposit Information:
ZAIK Number: | zpr87-044 |
---|---|
Depositing User: | Archive Admin |
Date Deposited: | 02 Apr 2001 00:00 |
Last Modified: | 25 Oct 2011 08:54 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/44 |