Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения - Турчина, В.А.; Федоренко, Н.К. (Проблемы управления и информатики, 2012)
Розглянуто вплив транзитивних дуг на оптимальність паралельного упорядкування, побудованого за алгоритмом, що базується на лексикографічному принципі. Запропоновано достатню умову, при якій транзитивні дуги не впливатимуть на оптимальність розв’язку, отриманого за цим алгоритмом. Досліджено клас графів, які задають нерозгалужені арифметичні вирази, та доведено, що для цих графів наявність транзитивних дуг також не впливатиме на оптимальність отриманого за алгоритмом розв’язку.