[Haskell-cafe] Matroids in Haskell

Henning Thielemann iakd0 at clusterf.urz.uni-halle.de
Mon Jan 17 07:02:27 EST 2005

On Fri, 14 Jan 2005, Michael Matsko wrote:

> Dimitri
>      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 mailing list