Efficient algorithms for simple matroid intersection problems

Harold N. Gabow, Robert E. Tarjan

Research output: Contribution to journalConference article

Abstract

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.

Original languageEnglish (US)
Article number4568015
Pages (from-to)196-204
Number of pages9
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs
StatePublished - Jan 1 1979
Externally publishedYes
Event20th Annual Symposium on Foundations of Computer Science, FOCS 1979 - San Juan, United States
Duration: Oct 29 1979Oct 31 1979

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Efficient algorithms for simple matroid intersection problems'. Together they form a unique fingerprint.

  • Cite this