Affiliations: Data General Corporation, Research Triangle Park, North Carolina, U.S.A.
Note: [1] The results of this paper were included in a presentation to the Third Annual ACM Symposium on Theory of Computing [21], and form part of the author’s recent doctoral dissertation [22], [23].
Abstract: A topological sorting of a tree is a linear ordering of its elements that preserves and extends their partial ordering in the tree. Any such arrangement of tree elements has a characteristic property, involving collective weights of initial or final substrings. Such properties have been investigated in connection with random walks, combinatorial arrangements, and the well-formed strings of parenthesis-free notations. Topological sortings of directed acyclic graphs exhibit a similar structure.
