Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems
Greg N. Frederickson, Mandayam A. Srinivas · SIAM Journal on Computing · 1989
Consider a matroid of rank n in which each element has a real-valued cost and one of $d > 1$ colors. A class of matroid intersection problems is studied in which one of the matroids is a partition matroid that specifies that a base has $q_j $ elements of color j, for $j = 1,2, \cdots ,d$. Relationships are characterized among the solutions to the family of problems generated when the vector $(q_1 ,q_2 , \cdots ,q_d )$ is allowed to range over all values that sum to n. A fast algorithm is given for solving such matroid intersection problems when d is small. A characterization is presented for how the solution changes when one element changes in cost. Data structures are given for updating the solution on-line each time the cost of an arbitrary matroid element is modified. Efficient update algorithms are given for maintaining a color-constrained minimum spanning tree in either a general or a planar graph. An application of the techniques to the problem of finding a minimum spanning tree with several degree-constrained vertices is described.