Аналіз графів з транзитивними дугами при побудові паралельних упорядкувань
Ключові слова:
задача паралельного упорядкування, транзитивні дуги, лексикографічне порівняння міток вершин
Анотація
При моделюванні виробничих процесів, в яких є відношення часткового порядку, використовуються орієнтовані ациклічні графи. Наявність транзитивних дуг в таких графах не впливає на виробничий процес та може впливати на точність алгоритмів, що розв’язують відповідні оптимізаційні задачі на графах. В роботі розглядаються питання саме такого впливу для задачі в загальній постановці та її часткового випадкуПереглядів анотації: 21 Завантажень PDF: 44
Опубліковано
2017-04-02
Розділ
Статті