FORESTS, FRAMES, AND GAMES - ALGORITHMS FOR MATROID SUMS AND APPLICATIONS

This paper presents improved algorithms for matroid-partitioning probl ems, such as finding a maximum cardinality set of edges of a graph tha t can be partitioned into k forests, and finding as many disjoint span ning trees as possible. The notion of a clump in a matroid sum is intr oduced, and efficient algorithms for clumps are presented. Application s of these algorithms are given to problems arising in the study of th e structural rigidity of graphs, the Shannon switching game, and other s.