Aim To research new characterization and circuit property of binary matroid. Methods Constract the modular pairs of hyperplanes of a a matroid. Results and Conclusion It is proved that a matroid M on finite set S is b...Aim To research new characterization and circuit property of binary matroid. Methods Constract the modular pairs of hyperplanes of a a matroid. Results and Conclusion It is proved that a matroid M on finite set S is binary if and only if for any two distinct hyper-planes H1 and H2, if H1H2S ,and H1 and H2 are modular pair, then S-(H1H2) is a hyperplande .And a necessary and sufficient condition for a binary matroid to have a k-circuit is obtained.展开更多
Let M be a matroid defined on a finite set E and L?⊂?E?. L is locked in M if??and ?are 2-connected, and . In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the lo...Let M be a matroid defined on a finite set E and L?⊂?E?. L is locked in M if??and ?are 2-connected, and . 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.展开更多
In this paper, we prove an analogous to a result of Erdös and Rényi and of Kelly and Oxley. We also show that there are several properties of k-balanced matroids for which there exists a threshold function.
In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an appro...In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an approximation algorithm, which consists of two sub-algorithms-the modified Edmonds' matroid partitioning algorithm and the exchange algorithm, for the problem. An estimation of the worst ratio for the algorithm is given.展开更多
Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.
文摘Aim To research new characterization and circuit property of binary matroid. Methods Constract the modular pairs of hyperplanes of a a matroid. Results and Conclusion It is proved that a matroid M on finite set S is binary if and only if for any two distinct hyper-planes H1 and H2, if H1H2S ,and H1 and H2 are modular pair, then S-(H1H2) is a hyperplande .And a necessary and sufficient condition for a binary matroid to have a k-circuit is obtained.
文摘Let M be a matroid defined on a finite set E and L?⊂?E?. L is locked in M if??and ?are 2-connected, and . 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.
文摘In this paper, we prove an analogous to a result of Erdös and Rényi and of Kelly and Oxley. We also show that there are several properties of k-balanced matroids for which there exists a threshold function.
基金Project (No. 10671177) supported by the National Natural Science Foundation of China
文摘In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an approximation algorithm, which consists of two sub-algorithms-the modified Edmonds' matroid partitioning algorithm and the exchange algorithm, for the problem. An estimation of the worst ratio for the algorithm is given.
文摘Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.
