Accession Number : ADA326053

Title :   Triangularization: A Two-Processor Scheduling Problem.

Descriptive Note : Doctoral thesis,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Haddad, Ramsey W.

PDF Url : ADA326053

Report Date : OCT 1990

Pagination or Media Count : 126

Abstract : We explore the following matrix problem: Given an n x n boolean matrix, is there a permutation of the rows and a permutation of the columns such that the resulting matrix is lower triangular? We show the relationship of this matrix problem to the two important scheduling problems: optimization of code for pipelined execution and microcode compaction for very long instruction computers. This matrix problem is unclassified-it is unknown whether it is NP-Complete or whether it can be solved by a polynomial time algorithm. We find several minor extensions that would make the problem NP-Complete. Also, we show polynomial algorithms for a number of special cases of the problem, and develop a number of interesting techniques in the process. We also explore approximation algorithms and lower bounds.

Descriptors :   *COMPUTER COMMUNICATIONS, *MATRICES(MATHEMATICS), *EXECUTIVE ROUTINES, *CONTROL SEQUENCES, ALGORITHMS, OPTIMIZATION, THESES, SCHEDULING, MULTIPROCESSORS, APPLIED MATHEMATICS, COMPUTER PROGRAM VERIFICATION, GAME THEORY, BOOLEAN ALGEBRA, NETWORK FLOWS, MATRIX THEORY, MULTIPROGRAMMING.

Subject Categories : Computer Programming and Software
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE