2016/06/15 by Brahim Chaourar, Chaourar, Brahim
Computer Science · Engineering · #52B40 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Primary 90C27 #Secondary 90C57 #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1606.05384
openalex publication_date 2016/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let M to be a matroid defined on a finite set E. A subset L of E is locked in M if L is 2-connected in M, the complement of L is 2-connected in the dual M*, and minr(L), r*(complement of L) is greater than 1. In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the locked subsets. We deduce that finding the maximum-weight basis of M is a polynomial problem for matroids with a polynomial number of locked subsets. This class of matroids is closed under 2-sums and contains uniform matroids.