|
|
|
Based on a general matroid construction of Edmonds, a short proof is described for a result of Nagamochi, Ishii, and Ito asserting that the k-sources in a source location problem form a matroid. The reduction allows us to derive a min-max formula for the minimum cardinality of a k-source.
Bibtex entry:
| AUTHOR | = | {Becker, Johanna and Frank, Andr{\'a}s}, |
| TITLE | = | {A quick proof for the matroidal structure of a source location problem}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2008}, |
| NUMBER | = | {QP-2008-01} |