For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Elementary Approach to the Principal Partition of a Matroid
Harihar NARAYANAN Manohar Narhar VARTAK
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1981/04/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Full Text: PDF(657.9KB)
>>Buy this Article
This paper deals with an elementary alternative approach to the notion of the principal partition of a matroid into strongly irreducible minors. This approach makes use of the matroid union theorem and the concept of the density of a matroid introduced in this paper. For a matroid M on S the density d(M)S/r(M). The principal partition of a matroid M on S is constructed by first constructing a partition of S called the P-sequence of M. On the resulting sub-sets irreducible minors are constructed. An irreducible minor is further partitioned into strongly irreducible minors by examining all its restrictions of density equal to its own. It is constructively shown that the P-sequence of a matroid M can be obtained by considering the intersections of sets of coloops of matroids obtained from M by repeated use of the matroid union () and the dualization (*) operator. It is shown that the principal partition for such matroids can be immediately constructed if the principal partition for the original matroid were given. Finally, efficient algorithms are outlined for constructing the principal partition.