Show simple item record

dc.contributor.authorBoyd, E. Andrew
dc.date.accessioned 2018-06-18T17:28:17Z
dc.date.available 2018-06-18T17:28:17Z
dc.date.issued 1988-05
dc.identifier.citation Boyd, E. Andrew. "A Combinatorial Abstraction of One Shortest Path Problem and Its Relationship to Greedoids." (1988) https://hdl.handle.net/1911/101643.
dc.identifier.urihttps://hdl.handle.net/1911/101643
dc.description.abstract 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.
dc.format.extent 30 pp
dc.title A Combinatorial Abstraction of One Shortest Path Problem and Its Relationship to Greedoids
dc.type Technical report
dc.date.note May 1988
dc.identifier.digital TR88-07
dc.type.dcmi Text


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record