Accession Number : ADA227221

Title :   Efficient Algorithms for a Class of Partitioning Problems.

Descriptive Note : Contractor rept.,

Corporate Author : INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA

Personal Author(s) : Iqbal, M. A. ; Bokhari, Shahid H.

Report Date : JUL 1990

Pagination or Media Count : 27

Abstract : The problem of optimally partitioning the modules of chain-or tree- like tasks over chain-structured or host-satellite multiple computer systems is addressed. This important class of problems includes many signal processing and industrial control applications. Prior research has resulted in a succession of faster exact and approximate algorithms for these problems. Polynomial exact and approximate algorithms are described for this class that are better than any of the previously reported algorithms. Our approach is based on a preprocessing step that condenses the given chain or tree structured task into a monotonic chain or tree. The partitioning of this monotonic task can then be carried out using fast search techniques. (jhd)

Descriptors :   *CONTROL THEORY, *SEARCHING, *SIGNAL PROCESSING, *INDUSTRIAL ENGINEERING, ALGORITHMS, EFFICIENCY, POLYNOMIALS.

Subject Categories : Statistics and Probability

Distribution Statement : APPROVED FOR PUBLIC RELEASE