Author | Korte, Bernhard. author |
---|---|
Title | Greedoids [electronic resource] / by Bernhard Korte, Rainer Schrader, Lรกszlรณ Lovรกsz |
Imprint | Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1991 |
Connect to | http://dx.doi.org/10.1007/978-3-642-58191-5 |
Descript | VIII, 214 p. online resource |
I. Introduction -- 1. Set Systems and Languages -- 2. Graphs, Partially Ordered Sets and Lattices -- II. Abstract Linear Dependence โ Matroids -- 1. Matroid Axiomatizations -- 2. Matroids and Optimization -- 3. Operations on Matroids -- 4. Submodular Functions and Polymatroids -- III. Abstract Convexity โ Antimatroids -- 1. Convex Geometries and Shelling Processes -- 2. Examples of Antimatroids -- 3. Circuits and Paths -- 4. Hellyโs Theorem and Relatives -- 5. Ramsey-type Results -- 6. Representations of Antimatroids -- IV. General Exchange Structures โ Greedoids -- 1. Basic Facts -- 2. Examples of Greedoids -- V. Structural Properties -- 1. Rank Function -- 2. Closure Operators -- 3. Rank and Closure Feasibility -- 4. Minors and Extensions -- 5. Interval Greedoids -- VI. Further Structural Properties -- 1. Lattices Associated with Greedoids -- 2. Connectivity in Greedoids -- VII. Local Poset Greedoids -- 1. Polymatroid Greedoids -- 2. Local Properties of Local Poset Greedoids -- 3. Excluded Minors for Local Posets -- 4. Paths in Local Poset Greedoids -- 5. Excluded Minors for Undirected Branchings Greedoids -- VIII. Greedoids on Partially Ordered Sets -- 1. Supermatroids -- 2. Ordered Geometries -- 3. Characterization of Ordered Geometries -- 4. Minimal and Maximal Ordered Geometries -- IX. Intersection, Slimming and Trimming -- 1. Intersections of Greedoids and Antimatroids -- 2. The Meet of a Matroid and an Antimatroid -- 3. Balanced Interval Greedoids -- 4. Exchange Systems and Gauss Greedoids -- X. Transposition Greedoids -- 1. The Transposition Property -- 2. Applications of the Transposition Property -- 3. Simplicial Elimination -- XI. Optimization in Greedoids -- 1. General Objective Functions -- 2. Linear Functions -- 3. Polyhedral Descriptions -- 4. Transversals and Partial Transversals -- 5. Intersection of Supermatroids -- XII. Topological Results for Greedoids -- 1. A Brief Review of Topological Prerequisites -- 2. Shellability of Greedoids and the Partial Tutte Polynomial -- 3. Homotopy Properties of Greedoids -- References -- Notation Index -- Author Index -- Inclusion Chart (inside the back cover)