A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids
type: Item
instance of: scholarly article
title: A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids
zbMATH Open document ID: 0644.05018
DOI: 10.1016/0166-218X(88)90040-6
author: Oskar Goecke
published in: Discrete Applied Mathematics
publication date: 1988-01-01T00:00:00Z
review text: A modified greedy algorithm is presented which determines an optimal solution for every weight function if and only if the hereditary set- system is a Gaussian elimination greedoid. This also leads to an algorithmic characterization of strong map relations between matroids.
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 4049666
zbMATH Keywords: greedy algorithm
zbMATH Keywords: Gaussian elimination greedoid
reviewed by: András Recski
MaRDI profile type: Publication
cites work: Matroids and the greedy algorithm
cites work: Systems of distinct representatives and linear algebra
cites work: Optimal assignments in an ordered set: An application of matroid theory
cites work: Q3796969
cites work: Strong maps of geometries
cites work: Q3928230
cites work: Q3338268
cites work: Non-interval greedoids and the transposition property
cites work: Greedoids and Linear Objective Functions
cites work: Note on Independence Functions
cites work: Q4111952
full work available at URL: 0166-218x(88)90040-6
OpenAlex ID: W1994443724
description: scientific article; zbMATH DE number 4049666