A Combinatorial Abstraction of One Shortest Path Problem and Its Relationship to Greedoids
Boyd, E. Andrew · Rice Research Repository (Rice University) · 1988
A natural generalization of the shortest path problem to arbitrary set systems is presented that captures a number of interesting problems, including the usual graph-theoretic shortest path problem and the problem of finding a minimum weight set on a matroid. Necessary and sufficient conditions for the solution of this problem by the greedy algorithm are then investigated. In particular, it is noted that it is necessary but not sufficient for the underlying combinatorial structure to be a greedoid, and the three extremely diverse collections of sufficient conditions taken from the greedoid literature are presented.