Efficient Algorithms for a Family of Matroid Intersection Problems
COLORADO UNIV AT BOULDER DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 in 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 On 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 Omn 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.
- Numerical Mathematics
- Theoretical Mathematics