zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Introduction to greedoids. (English) Zbl 0772.05026
Matroid applications, Encycl. Math. Appl. 40, 284-357 (1992).

[For the entire collection see Zbl 0742.00052.]

In 1981, Korte and Lovász introduced the concept of a greedoid to explain the underlying structure that leads to the success of various greedy algorithms in combinatorial optimization. Matroids are examples of greedoids but there are many greedoids which are not matroids. The authors use two well-known algorithms for finding a spanning tree in a connected graph to indicate the distinction between greedoids and matroids. Kruskal’s algorithm picks on edge at a time making sure that the current edge does not form a cycle with some set of edges that have already been chosen. Prim’s algorithm picks one edge at a time starting at some given vertex so that the current edge joins a visited vertex to an unvisited vertex. In both cases, the collection of feasible sequences of edges, that is sequences of edges that are generated by the allowed strategy, forms a greedoid. However, in the first case but not the second, any permutation of a feasible sequence is also feasible. The first case, where ordering of the edges is irrelevant, gives rise to a matroid; in the second case, order matters and one does not get a matroid.

Like matroids, greedoids can be defined in a multitude of equivalent ways. One such definition that is very like the independent-set definition of a matroid is that a greedoid is a finite set E together with a collection of (feasible) subsets of E such that (G1) every non-empty member X of contains a member x such that X-x, and (G2) if Y and Z are in and |Y|>|Z|, then there is an element y of Y-Z such that Zy.

This survey of greedoids and their properties begins with a discussion of the motivation for greedoids and a description of the basic examples. The latter include, in addition to matroids, greedoids that arise from branchings in graphs, from order ideals in partially ordered sets, and from convex hull closures in various spaces. The survey continues with discussions of various structural properties of greedoids, the links between greedoids and combinatorial optimization, and a greedoid polynomial akin to the Tutte polynomial in matroids. There is a section devoted to antimatroids, a class of greedoids that abstract properties of the convex hull operator in Euclidean spaces; another section looks at the poset of flats of a greedoid. The survey concludes with descriptions of some more specialized topics and with some historical remarks.

MSC:
05B35Matroids, geometric lattices (combinatorics)
90-02Research monographs (optimization)