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
Distribution Statement : APPROVED FOR PUBLIC RELEASE