An Elementary Approach to the Principal Partition of a Matroid

Harihar NARAYANAN; Manohar Narhar VARTAK

An Elementary Approach to the Principal Partition of a Matroid

Harihar NARAYANAN, Manohar Narhar VARTAK

Full Text Views

0

Cite this

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 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.

Publication: IEICE TRANSACTIONS on transactions Vol.E64-E No.4 pp.227-234

Publication Date: 1981/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Mathematics

Authors

Harihar NARAYANAN
Manohar Narhar VARTAK

Keyword

Cite this

Copy

Harihar NARAYANAN, Manohar Narhar VARTAK, "An Elementary Approach to the Principal Partition of a Matroid" in IEICE TRANSACTIONS on transactions, vol. E64-E, no. 4, pp. 227-234, April 1981, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e64-e_4_227/_p

Copy

@ARTICLE{e64-e_4_227,
author={Harihar NARAYANAN, Manohar Narhar VARTAK, },
journal={IEICE TRANSACTIONS on transactions},
title={An Elementary Approach to the Principal Partition of a Matroid},
year={1981},
volume={E64-E},
number={4},
pages={227-234},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - An Elementary Approach to the Principal Partition of a Matroid
T2 - IEICE TRANSACTIONS on transactions
SP - 227
EP - 234
AU - Harihar NARAYANAN
AU - Manohar Narhar VARTAK
PY - 1981
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E64-E
IS - 4
JA - IEICE TRANSACTIONS on transactions
Y1 - April 1981
AB - 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.
ER -