### Abstract

Given a matroid, where each element has a real-valued cost and is colored red or green, a minimum cost base with exactly q red elements is sought. 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 0(m log log n plus n alpha (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 0(m log n), the same as for the problem without the degree constraint.

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

Pages (from-to) | 196-204 |

Number of pages | 9 |

Journal | Annual Symposium on Foundations of Computer Science - Proceedings |

State | Published - Jan 1 1979 |

Event | Annu Symp Found Comput Sci Proc 20th - San Juan Bautista, PR Duration: Oct 29 1979 → Oct 31 1979 |

### All Science Journal Classification (ASJC) codes

- Hardware and Architecture