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.

Report Date:

1990-10-01

Pagination or Media Count:

126.0

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