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

• Федоренко Наталія Костянтинівна (фізико-математичні науки)

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"