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 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)

Descriptors :   (*GRAPHICS, ALGORITHMS), COMBINATORIAL ANALYSIS, OPERATORS(MATHEMATICS), SET THEORY, TOPOLOGY, THEOREMS

Subject Categories : Theoretical Mathematics
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE