• Апрель 28, 2008
  • Павел Наливайко
  • Динамические потоки
  • Аннотация
  • В докладе будут рассмотрены обобщения задачи о максимальном потоке: задача о лексикографически максимальном потоке, а также обзор задач решаемых с помощью динамических потоков. Динамические потоки являются обобщением обычных (статических) потоков в сетях. Помимо пропускных способностей дуги динамической сети обладают также транзитными временами, которые отражают время необходимое для того, чтобы переправить единицу потока вдоль дуги.