2017/02/23 by Brahim Chaourar, Chaourar, Brahim
Computer Science · Engineering · #52B40 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Primary 90C27 #Secondary 90C57 #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1702.07128
openalex publication_date 2017/02/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let M to be a matroid defined on a finite set E and L⊂ E. L is locked in M if M|L and M^*|(E\backslash L) are 2-connected, and min\r(L), r^*(E\backslash L)\ ≥ 2. 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 time problem for matroids with a polynomial number of locked subsets. This class of matroids is closed under 2-sums and contains the class of uniform matroids, the Vámos matroid and all the excluded minors of 2-sums of uniform matroids. We deduce also a matroid oracle for testing uniformity of matroids after one call of this oracle.