THE GREEDY ALGORITHM FOR FINITARY AND COFINITARY MATROIDS,
Abstract
The notion of a matroid was introduced by H. Whitney in 1932, in order to provide a unified treatment of the dependence structures of graph theory and linear algebra. In more recent years, the same notion has served to unify other areas of combinatorial mathematics. For example, the so-called greedy algorithm for finite matroids contains, as special cases, an algorithm for finding optimal assignments (of people to jobs, for example) and an algorithm for finding the shortest spanning tree of a graph (useful in the design of communication or transportation networks for certain purposes). The present report is concerned primarily with the extension of matroid theory so as to apply to infinite as well as finite systems. It contributes to matroid axiomatics and shows that the greedy algorithm applies to two important classes of infinite matroids. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1969
- Accession Number
- AD0689101
Entities
People
- Victor Klee
Organizations
- University of Washington