
For FullText 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
Publication
IEICE TRANSACTIONS (19761990)
Vol.E64
No.4
pp.227234 Publication Date: 1981/04/25
Online ISSN:
DOI:
Print ISSN: 00000000 Type of Manuscript: PAPER Category: Mathematics Keyword:
Full Text: PDF(657.9KB) >>Buy this Article
Summary:
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 Psequence of M. On the resulting subsets 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 Psequence 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.

