TY - JOUR

T1 - Efficient algorithms for simple matroid intersection problems

AU - Gabow, Harold N.

AU - Tarjan, Robert E.

N1 - Funding Information:
Section 2 gives a divide-and-conquer algorithm for this problem. Its efficiency is estimated on *This research was supported in part by National Science Foundation grant r'1CS7~-18~9.
Funding Information:
**This research was supported in part by National Science Foundation grant MCS75-22870, by the Office of Naval Research contract N00014-76-C-0688, and by a Guggenheim Fellowship.
Funding Information:
This research was supported in part by National Science Foundation grant MCS78-18909. This research was supported in part by National Science Foundation grant MCS75-22870, by the Office of Naval Research contract N00014-76-C-0688, and by a Guggenheim Fellowship.
Publisher Copyright:
© 1979 IEEE.

PY - 1979

Y1 - 1979

N2 - Given a matroid, where each element has a realvalued cost and is colored red or green; we seek a minimum cost base with exactly q red elements. This is a simple case of the matroid intersection problem. A general algorithm is presented. Its efficiency is illustrated in the special case of finding a minimum spanning tree with q red edges; the time is O(m log log n + n α (n,n) log n). Efficient algorithms are also given for job scheduling matroids and partition matroids. An algorithm is given for finding a minimum spanning tree where a vertex r has prespecified degree; it shows this problem is equivalent to finding a minimum spanning tree, without the degree constraint. An algorithm is given for finding a minimum spanning tree on a directed graph, where the given root r has prespecified degree; the time is O(m log n), the same as for the problem without the degree constraint.

AB - Given a matroid, where each element has a realvalued cost and is colored red or green; we seek a minimum cost base with exactly q red elements. This is a simple case of the matroid intersection problem. A general algorithm is presented. Its efficiency is illustrated in the special case of finding a minimum spanning tree with q red edges; the time is O(m log log n + n α (n,n) log n). Efficient algorithms are also given for job scheduling matroids and partition matroids. An algorithm is given for finding a minimum spanning tree where a vertex r has prespecified degree; it shows this problem is equivalent to finding a minimum spanning tree, without the degree constraint. An algorithm is given for finding a minimum spanning tree on a directed graph, where the given root r has prespecified degree; the time is O(m log n), the same as for the problem without the degree constraint.

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

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

U2 - 10.1109/SFCS.1979.14

DO - 10.1109/SFCS.1979.14

M3 - Conference article

AN - SCOPUS:85068686714

SP - 196

EP - 204

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SN - 0272-5428

M1 - 4568015

T2 - 20th Annual Symposium on Foundations of Computer Science, FOCS 1979

Y2 - 29 October 1979 through 31 October 1979

ER -