Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения

Abstract

Розглянуто вплив транзитивних дуг на оптимальність паралельного упорядкування, побудованого за алгоритмом, що базується на лексикографічному принципі. Запропоновано достатню умову, при якій транзитивні дуги не впливатимуть на оптимальність розв’язку, отриманого за цим алгоритмом. Досліджено клас графів, які задають нерозгалужені арифметичні вирази, та доведено, що для цих графів наявність транзитивних дуг також не впливатиме на оптимальність отриманого за алгоритмом розв’язку.

Transitive edges influence on the optimality of the scheduler built by the algorithm based on the lexicographic principle is considered. The sufficient condition when transitive edges don’t influence the optimality of the solution is given. Besides the class of graphs describing not branching arithmetic expressions is studied and it’s proved that transitive edges don’t influence optimality of the schedule for such graphs with transitive edges.