A series of contexts relative to a matroid*
1
Citation
16
Reference
10
Related Paper
Citation Trend
Abstract:
This paper presents some contexts relative to a matroid, which satisfy: all the closure operators derived from their Galois connections which to these contexts are the closure operator of the matroid.Using these results and ready-made algorithms for building up a concept lattice or an extent lattice, we believe that we may search out the class of all closed sets of a matroid, and meanwhile, create the construction of the dual of a matroid.Keywords:
Oriented matroid
Topics:
Weighted matroid
Oriented matroid
Cite
Citations (6)
Transversal (combinatorics)
Oriented matroid
Weighted matroid
Presentation (obstetrics)
Cite
Citations (23)
Las Vergnas's active orders are a collection of partial orders on the bases of a matroid which are derived from the classical notion of matroid activity. In this paper, we construct a generalization of Las Vergnas's external order which is defined on the independence complex of a matroid. We show that this poset is a refinement of the geometric lattice of flats of the matroid, and has the structure of a supersolvable join-distributive lattice. We uniquely characterize the lattices which are isomorphic to the external order of a matroid, and we explore a correspondence between matroid and antimatroid minors which arises from the poset construction.
Oriented matroid
Lattice (music)
Semilattice
Cite
Citations (1)
This paper proposes a framework to integrate rough sets with matroids. Specifically, we propose the lower and upper rough matroids which extend the matroid. They are established by the lower and upper approximations of generalized rough sets based on relations, respectively. As a generalization of the lower (upper) rough matroid, the lower (upper) rough greedoid is defined, and it also a generalization of the greedoid. Moreover, an axiom of poset matroid is provided by generalized rough sets based on relations. Finally, we prove that the poset matroid is a special case of the lower rough greedoid.
Oriented matroid
Weighted matroid
Cite
Citations (8)
Weighted matroid
Oriented matroid
Base (topology)
Cite
Citations (16)
Oriented matroid
Weighted matroid
Dual graph
Cite
Citations (7)
Let two linear matroids have the same rank in matroid intersection. A maximum linear matroid intersection (maximum linear matroid parity set) is called a basic matroid intersection (basic matroid parity set), if its size is the rank of the matroid. We present that enumerating all basic matroid intersections (basic matroid parity sets) is in NC, provided that there are polynomial bounded basic matroid intersections (basic matroid parity sets). For the graphic matroids, We show that constructing all basic matroid intersections is in NC if the number of basic graphic matroid intersections is polynomial bounded. To our knowledge, these algorithms are the first deterministic NC-algorithms for matroid intersection and matroid parity. Our result also answers a question of Harvey [8].
Weighted matroid
Oriented matroid
Parity (physics)
Cite
Citations (0)
A maximum linear matroid parity set is called a basic matroid parity set, if its size is the rank of the matroid. We show that determining the existence of a common base (basic matroid parity set) for linear matroid intersection (linear matroid parity) is in NC 2 , provided that there are polynomial number of common bases (basic matroid parity sets). For graphic matroids, we show that finding a common base for matroid intersection is in NC 2 , if the number of common bases is polynomial bounded. To our knowledge, these algorithms are the first deterministic NC algorithms for matroid intersection and matroid parity. We also give a new RNC 2 algorithm that finds a common base for graphic matroid intersection. We prove that if there is a black-box NC algorithm for Polynomial Identity Testing (PIT), then there is an NC algorithm to determine the existence of a common base (basic matroid parity set) for linear matroid intersection (linear matroid parity).
Weighted matroid
Oriented matroid
Parity (physics)
Cite
Citations (0)
Oriented matroid
Weighted matroid
Hyperplane
Rank (graph theory)
Cardinality (data modeling)
Cite
Citations (0)
Oriented matroid
Weighted matroid
Dual graph
Cite
Citations (4)