A Forward Lower Restricted Ordering Algorithm for Digraphs
Dale D. Olesky, T. A. Slater · SIAM Journal on Discrete Mathematics · 1992
The concept of forward lower restricted (FLR) orderings of digraphs arises naturally from the study of inherited entries in LU factorizations of matrices. Polynomial time algorithms are presented for deciding if a given ordered digraph is FLR ordered and for finding an FLR ordering of an arbitrary digraph. The latter algorithm also detects that a digraph is not FLR orderable. In addition, characterizations of FLR-ordered trees and maximal FLR-ordered digraphs are given. All of the results of this paper extend to inheritance of entries in the matrix L of the LU factorization and to inheritance in UL factorizations.