Name
Abstract | ||
|---|---|---|
Greedoids were introduced by the authors as generalizations of matroids providing a framework for the greedy algorithm. In
this paper they are studied from a structural aspect. Definitions of basic matroid-theoretical concepts such as rank and closure
can be generalized to greedoids, even though they loose some of their fundamental properties. The rank function of a greedoid
is only “locally” submodular. The closure operator is not monotone but possesses a (relaxed) Steinitz—McLane exchange property.
We define two classes of subsets, called rank-feasible and closure-feasible, so that the rank and closure behave nicely for
them. In particular, restricted to rank-feasible sets the rank function is submodular. Finally we show that Rado’s theorem
on independent transversals of subsets of matroids remains valid for feasible transversals of certain sets of greedoids. |
Year | DOI | Venue |
|---|---|---|
1983 | 10.1007/BF02579192 | Combinatorica |
Keywords | Field | DocType |
greedy algorithm,closure operator | Matroid,Discrete mathematics,Combinatorics,Closure operator,Generalization,Submodular set function,Greedy algorithm,Transversal (geometry),Greedoid,Mathematics,Monotone polygon | Journal |
Volume | Issue | ISSN |
3 | 3 | 1439-6912 |
Citations | PageRank | References |
16 | 5.40 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernhard Korte | 1 | 17 | 5.90 |
| László Lovász | 2 | 2640 | 881.45 |