Edited by Neil White
Publisher: Cambridge University Press
Print Publication Year: 1992
Online Publication Date:March 2010
Online ISBN:9780511662041
Hardback ISBN:9780521381659
Paperback ISBN:9780521119672
Chapter DOI: http://dx.doi.org/10.1017/CBO9780511662041.009
Subjects: Discrete Mathematics Information Theory and Coding
Image View Extract Fullview: Text View | Enlarge Image ‹ Previous Chapter › Previous Chapter
Introduction
Greedoids were invented around 1980 by B. Korte and L. Lovász. Originally, the main motivation for proposing this generalization of the matroid concept came from combinatorial optimization. Korte and Lovász had observed that the optimality of a ‘greedy’ algorithm could in several instances be traced back to an underlying combinatorial structure that was not a matroid – but (as they named it) a ‘greedoid’. In subsequent research greedoids have been shown to be interesting also from various non-algorithmic points of view.
The basic distinction between greedoids and matroids is that greedoids are modeled on the algorithmic construction of certain sets, which means that the ordering of elements in a set plays an important role. Viewing such ordered sets as words, and the collection of words as a formal language, we arrive at the general definition of a greedoid as a finite language that is closed under the operation of taking initial substrings and satisfies a matroid-type exchange axiom. It is a pleasant feature that greedoids can also be characterized in terms of set systems (the unordered version), but the language formulation (the ordered version) seems more fundamental.
Consider, for instance, the algorithmic construction of a spanning tree in a connected graph. Two simple strategies are: (1) pick one edge at a time, making sure that the current edge does not form a circuit with those already chosen; (2) pick one edge at a time, starting at some given node, so that the current edge connects a visited node with an unvisited node.
pp. i-vi
pp. vii-ix
List of Contributors : Read PDF
pp. x-x
pp. xi-xii
1 - Matroids and Rigid Structures : Read PDF
pp. 1-53
2 - Perfect Matroid Designs : Read PDF
pp. 54-72
3 - Infinite Matroids : Read PDF
pp. 73-90
4 - Matroidal Families of Graphs : Read PDF
pp. 91-105
5 - Algebraic Aspects of Partition Lattices : Read PDF
pp. 106-122
6 - The Tutte Polynomial and Its Applications : Read PDF
pp. 123-225
7 - Homology and Shellability of Matroids and Geometric Lattices : Read PDF
pp. 226-283
8 - Introduction to Greedoids : Read PDF
pp. 284-357
pp. 358-363