Matroids and more generally, greedoids, are special classes of hypergraphs. For these classes greedy algorithms give optimal solutions for optimization problems, and have low polynomial time complexity. Special cases are
- Kruskal's algorithm for finding minimal spanning trees, and
- Dijkstra's algorithm for finding shortest paths, both in weighted graphs.
There are many other matroid algorithms. See for example
- Bixby and Cunningham's chapter in the Handbook of Combinatorics, volume 1, or
- Jungnickel's book Graphs, networks and algorithms.