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

• Published in: Проблемы управления и информатики
• Date: 2012
• Main Authors: Турчина, В.А., Федоренко, Н.К.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2012
• Subjects: Оптимальное управление и методы оптимизации
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/207448
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения / В.А. Турчина, Н.К. Федоренко // Проблемы управления и информатики. — 2012. — № 1. — С. 62–71. — Бібліогр.: 3 назв. - рос.

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