Efficient Algorithms for Simple Matroid Intersection Problems

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.

Authors

• Harold N. Gabow
• Robert Endre Tarjan

Keywords

• Partitioning algorithms
• Tree graphs
• Computer science
• Scheduling algorithm
• Bipartite graph
• Polynomials
• Cost function
• Computer networks
• Communication networks
• Contracts
• Intersection Problem
• Matroid Intersection
• Directed Graph
• Red Edge
• Spanning Tree
• Job Scheduling
• Active Components
• Set Of Elements
• Selection Algorithm
• Implementation Of Approach
• Time Slot
• Elements
• Linear Time
• Original Graph
• Tree Edges
• Active Edge
• N Log N
• Green Edges