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.

Matroid intersection problems are 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 maintaining the solutions to several such problems online under the operation of changing an edge cost. 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 integer release times and deadlines.

A parallel algorithm for Gaussian elimination (GE) is described, which solves a linear system of size n using m ≤ n parallel processors and a shared random access memory. Converting the serial GE algorithm to parallel form involves scheduling its computation DAG (directed acyclic graph) on m processors. A lower bound for schedule length is established for dense GE DAG's and it is proved that the proposed algorithm produces schedules which achieve these bounds. Finally, both the construction and execution of the schedule are incorporated into a single concurrent program which is shown to run in optimal time.