Efficient algorithms for matroid sums

Abstract

Matroid theory is the theory of sets in a finite universe. The term independent is borrowed from linear algebra as is most of the terminology. Many combinatorial problems can be modeled by matroids. A solution is expressed as a maximum cardinality set, also referred to as a base, or some other object in matroid theory. This thesis investigates problems that can be modeled with matroid sums. Matroid sums are matroids that can be decomposed into a number of simpler matroids. Typical problems that can be modeled with matroid sums are finding k disjoint spanning trees, the Shannon switching game, finding the arboricity and pseudorarboricity, and problems arising in the study of rigidity of structures. Further problems that can be modeled with matroid sums are the graphic and bicircular packing problem and maximum cardinality bipartite matching. Except for the last the matroid algorithms presented for the above problems yield improved time bounds. This thesis also investigates the theoretical properties of matroid sums. The concept of a clump is introduced. Clumps help to design and analyze algorithms on matroid sums. They lead to the notion of a top clump, which in turn leads to an invariant of a matroid sum and, a fortiori, to a family of invariants of a graph. They generalize another invariant, the principal partition introduced by Kishi and Kajitani and its generalization, the k-minor introduced by Bruno.

Cite this paper

@article{westermann1988efficient,
  title = {{Efficient algorithms for matroid sums}},
  author = {Westermann, Herbert},
  year = {1988}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.

Related papers