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
SN - 0272-5428
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
M1 - 4568015
T2 - 20th Annual Symposium on Foundations of Computer Science, FOCS 1979
Y2 - 29 October 1979 through 31 October 1979
ER -