
Accession Number : ADA326053
Title : Triangularization: A TwoProcessor 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 unclassifiedit is unknown whether it is NPComplete or whether it can be solved by a polynomial time algorithm. We find several minor extensions that would make the problem NPComplete. 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