DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# Accession Number:

## ADA326053

# Title:

## Triangularization: A Two-Processor Scheduling Problem.

# Descriptive Note:

## Doctoral thesis,

# Corporate Author:

## STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

# 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.

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#