On-line updating of solutions to a class of matroid intersection problems (Q1090461)

The class of matroid intersection problems is considered in which one of the matroids is a partition matroid specifying that exactly q elements in the solution must be red, and the rest green. 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 red-green minimum spanning tree in both a general and a planar graph, and a red-green job schedule for unit- time jobs with deadlines.