Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142919 | Operations Research Letters | 2008 | 4 Pages |
Abstract
Given a weighted matroid MM and a positive integer KK, the KKth best base of MM problem is to find KK distinct minimum (or maximum) bases regarding the weight function. This problem is NP-hard. We prove that it is polynomial for 2-sums of uniform matroids and a fixed number of kk-sums of series parallel graphs, M(K4)M(K4), W3W3, Q6Q6 and P6P6.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Brahim Chaourar,