
Accession Number : AD0689101
Title : THE GREEDY ALGORITHM FOR FINITARY AND COFINITARY MATROIDS,
Corporate Author : WASHINGTON UNIV SEATTLE
Personal Author(s) : Klee,Victor
Report Date : MAY 1969
Pagination or Media Count : 33
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 socalled 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)
Descriptors : (*GRAPHICS, ALGORITHMS), COMBINATORIAL ANALYSIS, OPERATORS(MATHEMATICS), SET THEORY, TOPOLOGY, THEOREMS
Subject Categories : Theoretical Mathematics
Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE