Forests, frames, and games: algorithms for matroid sums and applications

This paper presents improved algorithms for matroid partitioning problems, such as finding a maximum cardinality set of edges of a graph that can be partitioned into k forests. The notion of a clamp in a matroid sum is introduced. Efficient algorithms for problems involving clumps are presented. Applications of these algorithms to problems arising in the study of structural rigidity of graphs, the Shannon switching game and others are given.