### Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 80-131 |

Number of pages | 52 |

Journal | Journal of Algorithms |

Volume | 5 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 1984 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Computational Mathematics
- Control and Optimization
- Computational Theory and Mathematics

### Cite this

*Journal of Algorithms*,

*5*(1), 80-131. https://doi.org/10.1016/0196-6774(84)90042-7

}

*Journal of Algorithms*, vol. 5, no. 1, pp. 80-131. https://doi.org/10.1016/0196-6774(84)90042-7

**Efficient algorithms for a family of matroid intersection problems.** / Gabow, Harold N.; Tarjan, Robert Endre.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Efficient algorithms for a family of matroid intersection problems

AU - Gabow, Harold N.

AU - Tarjan, Robert Endre

PY - 1984/1/1

Y1 - 1984/1/1

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 - https://doi.org/10.1016/0196-6774(84)90042-7

DO - https://doi.org/10.1016/0196-6774(84)90042-7

M3 - Article

VL - 5

SP - 80

EP - 131

JO - Journal of Algorithms

JF - Journal of Algorithms

SN - 0196-6774

IS - 1

ER -