17761

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Доклад

Название: 

A Graphical Approach to Solve Combinatorial Problems: Algorithms and Some Computational Results

Электронная публикация: 

Да

Наименование конференции: 

  • 14th IFAC Symposium on Information Control Problems in Manufacturing (INCOM’12, Bucharest, Romania)

Наименование источника: 

  • Proceedings of the 14th IFAC Symposium on Information Control Problems in Manufacturing (INCOM’12, Bucharest)

Город: 

  • Bucharest

Издательство: 

  • University Politehnica of Bucharest, CIMR Research Centre

Год издания: 

2012

Страницы: 

403-408
Аннотация
In this paper, we present a modification of dynamic programming algorithms (DPA), which we denote as graphical algorithms (GrA). For some single machine scheduling problems, it is shown that the time complexity of the GrAis less than the time complexity of the standard DPA. Moreover, the average running time of the GrAis often essentially smaller. A GrAcan also solve large-scale instances and instances, where the parameters are not integer. For some problems,GrAhas a polynomial time complexity in contrast to a pseudo-polynomial complexity of aDPA.

Библиографическая ссылка: 

Лазарев А.А., Гафаров Е.Р., Werner F. A Graphical Approach to Solve Combinatorial Problems: Algorithms and Some Computational Results / Proceedings of the 14th IFAC Symposium on Information Control Problems in Manufacturing (INCOM’12, Bucharest). Bucharest: University Politehnica of Bucharest, CIMR Research Centre, 2012. С. 403-408.