TY - JOUR

T1 - Efficient algorithms for a family of matroid intersection problems

AU - Gabow, Harold N.

AU - Tarjan, Robert E.

N1 - Funding Information:
*A preliminary version of this paper appeared in the Proceedings of the 20th Annual Symposium on the Foundations of Computer Science, San Juan, Puerto Rico [GTl]. +The work of this author was supported in part by the National Science Foundation under Grant MCS 78-18909. *Current address: AT&T, Bell Laboratories, Murray Hill, N.J. 07974. The work of this author was supported in part by the National Science Foundation under Grant MCS75-22870, by the Office of Naval Research, Contract N 00014-76-C-0688, and by a Guggenheim Fellowship.

PY - 1984/3

Y1 - 1984/3

N2 - Consider a matroid where each element has a real-valued cost and a color, red or green; a base is sought that contains q red elements and has smallest possible cost. An algorithm for the problem on general matroids is presented, along with a number of variations. Its efficiency is demonstrated by implementations on specific matroids. In all cases but one, the running time matches the best-known algorithm for the problem without the red element constraint: On graphic matroids, a smallest spanning tree with q red edges can be found in time O(n log n) more than what is needed to find a minimum spanning tree. A special case is finding a smallest spanning tree with a degree constraint; here the time is only O(m + n) more than that needed to find one minimum spanning tree. On transversal and matching matroids, the time is the same as the best-known algorithms for a minimum cost base. This also holds for transversal matroids for convex graphs, which model a scheduling problem on unit-length jobs with release times and deadlines. On partition matroids, a linear-time algorithm is presented. Finally an algorithm related to our general approach finds a smallest spanning tree on a directed graph, where the given root has a degree constraint. Again the time matches the best-known algorithm for the problem without the red element (i.e., degree) constraint.

AB - Consider a matroid where each element has a real-valued cost and a color, red or green; a base is sought that contains q red elements and has smallest possible cost. An algorithm for the problem on general matroids is presented, along with a number of variations. Its efficiency is demonstrated by implementations on specific matroids. In all cases but one, the running time matches the best-known algorithm for the problem without the red element constraint: On graphic matroids, a smallest spanning tree with q red edges can be found in time O(n log n) more than what is needed to find a minimum spanning tree. A special case is finding a smallest spanning tree with a degree constraint; here the time is only O(m + n) more than that needed to find one minimum spanning tree. On transversal and matching matroids, the time is the same as the best-known algorithms for a minimum cost base. This also holds for transversal matroids for convex graphs, which model a scheduling problem on unit-length jobs with release times and deadlines. On partition matroids, a linear-time algorithm is presented. Finally an algorithm related to our general approach finds a smallest spanning tree on a directed graph, where the given root has a degree constraint. Again the time matches the best-known algorithm for the problem without the red element (i.e., degree) constraint.

UR - http://www.scopus.com/inward/record.url?scp=0041110806&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0041110806&partnerID=8YFLogxK

U2 - 10.1016/0196-6774(84)90042-7

DO - 10.1016/0196-6774(84)90042-7

M3 - Article

AN - SCOPUS:0041110806

SN - 0196-6774

VL - 5

SP - 80

EP - 131

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -