Affordable Access

Publisher Website

On the [formula omitted]th best base of a matroid

Authors
Journal
Operations Research Letters
0167-6377
Publisher
Elsevier
Publication Date
Volume
36
Issue
2
Identifiers
DOI: 10.1016/j.orl.2007.05.007
Keywords
  • [Formula Omitted]Th Best Base Of A Matroid
  • Base Of A Matroid
  • Polytope
  • Extreme Point
  • Facet
  • [Formula Omitted]-Sums Of Graphs

Abstract

Abstract Given a weighted matroid M and a positive integer K , the K th best base of M problem is to find K 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 k -sums of series parallel graphs, M ( K 4 ) , W 3 , Q 6 and P 6 .

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

[formula omitted]-fuzzy matroids

on Fuzzy Sets and Systems Jan 01, 2009

The number of rank-kflats in a matroid with no [fo...

on Journal of Combinatorial Theor...

On the structure of the [formula omitted]-vector o...

on European Journal of Combinator...

The number of rank-kflats in a matroid with no [fo...

on Journal of Combinatorial Theor...
More articles like this..