Talk:Greedoid

Untitled

Surely matroids go back to Whitney? Charles Matthews 06:56, 20 May 2004 (UTC)[reply]

Am I right to say that the only way in which greedoids generalize matroids is by relaxing the hereditary property, that all subsets of a feasible set are feasible? That's how it seems here. Deco 3 July 2005 23:01 (UTC)

The exchange property is technically not stated correctly -- I think it should say that there exists x ∈ X-Y rather than just x ∈ X. 65.189.192.86 07:09, 22 December 2005 (UTC)[reply]

The paragraph about Dijkstra's algorithm is not correct. Using the algorithm described there, you will end up with the arborescence with minimal cost, not with arborescence containing all shortest paths. I suppose this article contain enough information: http://www.caam.rice.edu/caam/trs/88/TR88-07.pdf — Preceding unsigned comment added by Desikblack (talk • contribs) 11:27, 23 March 2011 (UTC)[reply]

Shouldn't the definition for the interval greedoid be:

if A, B, C ∈ F with A ⊆ B ⊆ C, then, for all x ∈ E\C, (A∪{x} ∈ F and C∪{x} ∈ F) implies B∪{x} ∈ F

Instead of:

if A, B, C ∈ F with A ⊆ B ⊆ C, then, for all x ∈ F\C, (A∪{x} ∈ F and C∪{x} ∈ F) implies B∪{x} ∈ F

--196.215.127.206 (talk) 15:00, 28 September 2012 (UTC)[reply]

In the definition of a matroid, non-emptiness is required. I think it is not possible to deduce this from the axioms of a greedoid together with the interval property without lower bounds. So one should either add this requirement to the definition of greedoid, or write "A matroid is a greedoid (F,E) with $F\neq \emptyset$ (or $\emptyset \in F$ ) that satisfies the Interval Property without Lower Bounds." --Maformatiker (talk) 13:01, 23 October 2015 (UTC)[reply]

Shouldn't Prim's algorithm correspond to the line search greedoid instead of the vertex search greedoid?

It just seems that the ground set should consist of edges of a graph, instead of vertices. --Svennik (talk) 15:46, 7 February 2024 (UTC)[reply]

It looks like the maximum weighted feasible set for a vertex search greedoid would simply consist of the connected component of its root vertex. Seems kind of trivial to me? Maybe the order in which the vertices are visited in the greedy algorithm for the vertex search greedoid has some connection to Dijkstra's algorithm, which enumerates vertices from closest to furthest from a source vertex. --Svennik (talk) 15:55, 7 February 2024 (UTC)[reply]