Efficient algorithms for a family of matroid intersection problems

Harold N. Gabow, Robert Endre Tarjan

Research output: Contribution to journalArticle

49 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)80-131
Number of pages52
JournalJournal of Algorithms
Volume5
Issue number1
DOIs
StatePublished - Jan 1 1984

Fingerprint

Matroid Intersection
Matroid
Efficient Algorithms
Spanning tree
Minimum Spanning Tree
Costs
Release Time
Directed graphs
Graph Model
Deadline
Linear-time Algorithm
Family
Directed Graph
Scheduling Problem
Scheduling
Partition
Roots
Color
Unit

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Control and Optimization
  • Computational Theory and Mathematics

Cite this

@article{0240448800bf407982f447cf572a959f,
title = "Efficient algorithms for a family of matroid intersection problems",
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.",
author = "Gabow, {Harold N.} and Tarjan, {Robert Endre}",
year = "1984",
month = "1",
day = "1",
doi = "https://doi.org/10.1016/0196-6774(84)90042-7",
language = "English (US)",
volume = "5",
pages = "80--131",
journal = "Journal of Algorithms",
issn = "0196-6774",
publisher = "Academic Press Inc.",
number = "1",

}

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

In: Journal of Algorithms, Vol. 5, No. 1, 01.01.1984, p. 80-131.

Research output: Contribution to journalArticle

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 -