The matroid parity problem is a common generalization of the matching problem for graphs. The matroid intersection problem and its engineering applications are also known. It has been shown that the matroid parity problem is generally unsolvable in a polynomial‐bounded running time. The concept of principal partition has recently been extended to matroids with parity condition as well as to 2‐polymatroids and a certain class of matroids for which the matroid parity problem can be solved by a polynomial bounded algorithm has been charcterized. This paper shows that the central minor plays an important role when using the concept of principal partition in the matroid parity problem and generalizes the concept of principal partition of a matroid into its strongly irreducible minors pairs. Then we characterize the properties of strongly irreducible minors pairs and the critical sets pairs which give these minors pairs. Finally, we give a class of matroids for which one can show the existence of such a principal partition and solve the parity problem by a polynomial‐bounded algorithm by using the concept of the so‐called F0‐strongly irreducible minors pairs. At the same time, we show that a strongly irreducible minor called the F0‐ minimal central minor plays an essential role in the theory of principal partition in parity problems.
|Electronics and Communications in Japan (Part I: Communications)
|Published - 1985
ASJC Scopus subject areas
- コンピュータ ネットワークおよび通信