Investigation of the Effect of Transitive Edges on the Optimality of Some Algorithms for Parallel Ordering

摘要

The effect of the transitive edges on the optimality of parallel ordering constructed by the algorithm based on the lexicographical principle is considerd. The sufficient condition under which the transitive edges will not affect the optimal solutions, obtained with this algorithm, is proposed. The class of graphs, giving the nonbranching arithmetic expressions is investigated, and it is proved that for these graphs the existence of transitive edges also will not affect the optimality of the solution, obtained by the algorithm.