A Note on k-Limited Maximum Base

Introduction Findingaspecialmaximumbaseofamatroidis aninterestingproblem.Theproblemhasmanyappli cationsinnetworks,graphtheory,andcombinatorial optimization.InRef.1],Edmondsgavearelation betweenamatroidandgreedyalgorithm,which answeredhowtofindthemaximumb…

A Note on k-Limited Maximum Base

The problem of k-llmited maximum base was specified into two special problems of k-limited maximum base; that is, let subset D of the problem of k-limited maximum base be an independent set and a circuit of the matroid, respectively. It was proved that under this circumstance the collections of k-limited base satisfy base axioms. Then a new matroid was determined, and the problem of k-limited maximum base was transformed to the problem of maximum base of this new matroid. Aiming at the problem, two algorithm% which in essence are greedy algorithms based on former matroid, were presented for the two special problems of k- limited maximum base. They were proved to be reasonable and more efficient than the algorithm presented by Ma Zhongfan in view of the complexity of algorithm.