Horn's algorithm for weighted mean flow scheduling with treelike precedence constraints is reexamined. A new analysis of an efficient implementation of Horn's algorithm shows an O(n log n) complexity. This is an improvement on the known O(n2) complexity of this algorithm. An application of Horn's algorithm to a problem of optimal scheduling of a treelike communication network is presented.
All Science Journal Classification (ASJC) codes
- Information Systems
- Hardware and Architecture
- Computer Networks and Communications