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 egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2008}, |
NUMBER | = | {QP-2008-01} |