*Technical Report B-00-05*

*March 1, 2000*

**Rajeev Wankar**

**N.S.Chaudhari*
Elfriede Fehr**

**Freie Universität Berlin, Institut für Informatik**

**{fehr, wankar}@inf.fu-berlin.de**

***School of Computer Science, DAVV Indore, India**

An algorithm for the triangularization of a matrix whose graph is a
directed acyclic graph, popularly known as* dag*, is presented. One
of the algorithms for obtaining this special form has been given by Sargent
and Westerberg. Their approach is practically good but sequential in nature
and cannot be parallelised easily. In this work we present a parallel algorithm
which is based on the observation that, if we find the transitive closure
matrix of a directed acyclic graph, count the number of entries in each
row, sort them in the ascending order of their values and rank them accordingly,
we get a lower triangular matrix. We show that all these operations can
be done using 3-d CD-PARBS (Complete Directed PARBS) in constant time.
The same approach can be used for the block cases, producing the same relabelling
as produced by Tarjan's algorithm, in constant time. To the best of our
knowledge, it is the first approach to solve such problems using directed
PARBS.

`Get the report in postscript
or in PDF
format.`

Server: fubinf.inf.fu-berlin.de

File: pub/reports/tr-b-00-05.ps.gz