Наукові публікації університету

Problem Statements for k-Node Shortest Path and k-Node Shortest Cycle in a Complete Graph*

The author formulates mixed Boolean linear programming problems to find the shortest route and the shortest cycle that pass through the given number of nodes in a complete graph. Their special cases provide formulations of problems for finding the shortest Hamiltonian path and the shortest Hamiltonian cycle. The problems include no more than 2n2 variables and no more than (n + 1)2 constraints, where n is the number of nodes of the complete graph.

ID: 182525
Кількість показів: 35
дата змінення: 14.11.2016 18:56:43
Ким змінено (ім'я): (cyb13) Дмитро Терлецький
Вид роботи:  Наукова публікація
Тип роботи:  Наукова стаття
Кількість сторінок:  5
Рік видання:  2016
Звітний рік:  2016
Видання:  Кібернетика і системний аналіз
Том:  52
Випуск, частина:  1
Номери сторінок:  71-75
Галузь науки:  Інформатика
Автори,співробітники Університету:  Стецюк Петро Іванович
Кафедра / Відділ:  Інформаційних систем
№ теми:  16КФ015-01
Посилання на статтю (посилання на рецензію в журналі (для монографій):  http://link.springer.com/article/10.1007/s10559-016-9801-x
Ключові слова:  complete graph shortest path linear programming problem Hamiltonian path Hamiltonian cycle traveling salesman problem.
Опубліковано за рішенням Вченої ради:  ні
Інститут/Факультет:  Факультет комп'ютерних наук та кібернетики

Повернення до списку

Вгору