Аналіз графів з транзитивними дугами при побудові паралельних упорядкувань

  • V. A. Turchina
  • L. R. Dzhanashiya
Ключові слова: задача паралельного упорядкування, транзитивні дуги, лексикографічне порівняння міток вершин

Анотація

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

Переглядів анотації: 21
Завантажень PDF: 44
Опубліковано
2017-04-02