[Haskell-cafe] Matroids in Haskell
iakd0 at clusterf.urz.uni-halle.de
Mon Jan 17 07:02:27 EST 2005
On Fri, 14 Jan 2005, Michael Matsko wrote:
> Matriods are generalization of vector spaces. Basically, they are
> defined by a set of linear dependence axioms and basis exchange
> properties. Oxley's "Matriod Theory" is the standard reference. There
> are a multitude of equivalent formulations.
... and the most spectacular result is, that a greedy algorithm for a
problem is optimal if and only if the problem has Matroid structure.
More information about the Haskell-Cafe