Paper Info
Title
A one-way array algorithm for matroid scheduling
Abstract
. The greedy algorithm is a standard paradigm for solving matroid optimization problemson sequential computers. This paper presents a greedy algorithm suitable for a fully-pipelinedlinear array of processors, a generalization of Huang's algorithm [Hua90] for minimum spanning trees.Application of the algorithm to uniprocessor scheduling with release times and deadlines is discussedin detail. A key feature of the algorithm is its use of matroid contraction.1. Introduction. Algorithms on...
Year
DOI
Venue
1991
10.1145/113379.113411
SPAA
Keywords
Field
DocType
one-way array algorithm,matroid scheduling,minimum spanning tree,greedy algorithm
Matroid,Discrete mathematics,Combinatorics,Computer science,Prim's algorithm,Greedy algorithm,Matroid partitioning,Circuit rank,Weighted matroid,Reverse-delete algorithm,Kruskal's algorithm
Conference
ISBN
Citations 
PageRank 
0-89791-438-4
0
0.34
References 
Authors
8
1
Name
Order
Citations
PageRank
Matthias F. M. Stallmann116619.38