Abstract:
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.Keywords:
Oriented matroid
Weighted matroid
It is well known that a matroid is a transversal matroid if and only if it is a matching matroid (in the sense that it is the restriction of the matching structure of some graph to a subset of its vertices). A simple proof of that result is now known and in this paper it is used to answer the long-standing question of which transversal matroids are “strict” matching matroids; i.e. actually equal to the matching structure of a graph. We develop a straightforward test of “coloop-surfeit” that can be applied to any transversal matroid, and our main theorem shows that a transversal matroid is a strict matching matroid if and only if it has even rank and coloop-surfeit. Furthermore, the proofs are algorithmic and enable the construction of an appropriate graph from any presentation of a strict matching matroid.
Weighted matroid
Oriented matroid
Transversal (combinatorics)
Cite
Citations (1)
Weighted matroid
Oriented matroid
Cite
Citations (6)
This article first uses the matroid language to difine the new concepts of graph as the new concepts of matroid, and then we use the matroid language to translate the new results which Goddyn and Heuvel have attained in graph into the new results of matroid. Last, we will prove these new results by the method of matroid.
Oriented matroid
Weighted matroid
Cite
Citations (0)
Matroid theory is the theory of sets in a finite universe. The term independent is borrowed from linear algebra as is most of the terminology. Many combinatorial problems can be modeled by matroids. A solution is expressed as a maximum cardinality set, also referred to as a base, or some other object in matroid theory. This thesis investigates problems that can be modeled with matroid sums. Matroid sums are matroids that can be decomposed into a number of simpler matroids. Typical problems that can be modeled with matroid sums are finding k disjoint spanning trees, the Shannon switching game, finding the arboricity and pseudorarboricity, and problems arising in the study of rigidity of structures. Further problems that can be modeled with matroid sums are the graphic and bicircular packing problem and maximum cardinality bipartite matching. Except for the last the matroid algorithms presented for the above problems yield improved time bounds.
This thesis also investigates the theoretical properties of matroid sums. The concept of a clump is introduced. Clumps help to design and analyze algorithms on matroid sums. They lead to the notion of a top clump, which in turn leads to an invariant of a matroid sum and, a fortiori, to a family of invariants of a graph. They generalize another invariant, the principal partition introduced by Kishi and Kajitani and its generalization, the k-minor introduced by Bruno.
Weighted matroid
Oriented matroid
Disjoint sets
Cite
Citations (5)
The ground set for all matroids in this paper is the set of all edges of a complete graph. The notion of a {\it maximum matroid for a graph} $G$ is introduced, and the existence and uniqueness of the maximum matroid for any graph $G$ is proved. The maximum matroid for $K_3$ is shown to be the cycle (or graphic) matroid. This result is pursued in two directions - to determine the maximum matroid for the $m$-cycle $C_m$ and to determine the maximum matroid for the complete graph $K_m$. The maximum matroid for $K_4$ is the matroid whose bases are the Laman graphs, related to structural rigidity of frameworks in the plane. The maximum matroid for $K_5$ is related to a famous 153 year old open problem of J. C. Maxwell.
Weighted matroid
Oriented matroid
Dual graph
Cite
Citations (2)
The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Lovász (1980) showed that this problem admits a min-max formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem.
Weighted matroid
Oriented matroid
Parity (physics)
Cite
Citations (10)
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 simple characterization of the set MCOLOOP of coloops in the strict matching matroid of an undirected graph G - (V,n) is provided, which allows the Edmonds decomposition of G to be produced in O(|V|5/2) Based on this decomposition, we have the following results' Two graphs associated with G are produced in . One is a bipartite graph with at most edges whose transversal matroid is isomorphic to the strict matching matroid of G; the other is a directed graph with at most edges, represending the strict gammoid dual to the strict matching matroid. The matroid components of the strict matching matroid of G are produced in , where ∂ is the matching defect of G and K(G) number of component G(V MCOLOOP). We show how to list the bases of the strict matching matroid of G and also calculate its Whitney and Tutle polynomials, in where N is the number of bases in the matroid.
Weighted matroid
Oriented matroid
Cite
Citations (1)
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)
The ground set for all matroids in this paper is the set of all edges of a complete graph. The notion of a {\it maximum matroid for a graph} $G$ is introduced, and the existence and uniqueness of the maximum matroid for any graph $G$ is proved. The maximum matroid for $K_3$ is shown to be the cycle (or graphic) matroid. This result is pursued in two directions - to determine the maximum matroid for the $m$-cycle $C_m$ and to determine the maximum matroid for the complete graph $K_m$. The maximum matroid for $K_4$ is the matroid whose bases are the Laman graphs, related to structural rigidity of frameworks in the plane. The maximum matroid for $K_5$ is related to a famous 153 year old open problem of J. C. Maxwell.
Weighted matroid
Oriented matroid
Dual graph
Cite
Citations (3)