Алгоритм нахождения k максимальных потоков
Ключевые слова:
сеть связи с коммутацией пакетов, пропускная способность соединения, задача о максимальном потокеАннотация
В работе предлагается оригинальный алгоритм решения прикладной задачи теории графов о нахождении k максимальных потоков между двумя заданными вершинами графа. Описываемый подход представляет собой комплексное применение в едином оптимизационном цикле алгоритма Форда-Фалкерсона (Эдмондса-Карпа или Диница) и алгоритма построения усеченного дерева состояний в ширину.Литература
Ш. Качество обслуживания в сетях IP: пер. с англ. // М.: Издательский дом "Вильямис". 2003. 368 с.
2. Кучерявый Е.А. Управление трафиком и качество обслуживания в сети Интернет // СПб.: Наука и Техника. 2004. 336 с.
3. Ford L.R., Fulkerson Jr. Fulkerson, D.R. Maximal Flow through a Network // Canadian Journal of Mathematics. 1956. pp. 399–404.
4. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 3-е издание // М.: "Вильямс". 2013. 1323 с.
5. Dinitz Y. Dinitz' Algorithm: The Original Version and Even's Version // Theoretical Computer Science: Essays in Memory of Shimon Even. Springer, 2006. pp. 218–240.
6. Arora S., Hazan E., Kale S. The multiplicative weights update method: A meta-algorithm and applications // Theory OF Computing. 2012. pp. 121–164.
7. Christiano P., Kelner J., Madry A., Spielman D., Teng S. Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs // Proceedings of the forty-third annual ACM symposium on Theory of computing (STOC 2011). 2011. pp. 273–282.
8. Lee Y.T., Rao S., Srivastava N. A new approach to computing maximum flows using electrical flows // Proceedings of the forty-fifth annual ACM symposium on Theory of computing (STOC 2013). 2013. pp. 755–764.
9. Кристофидес Н. Теория графов. Алгоритмический подход // М.: Мир. 1978. 432 с.
10. Нечепуренко М.И., Попков В.К., Майнагашев С.М. Алгоритмы и программы решения задач на графах и сетях // Новосибирск: Наука. Сиб. отделение. 1990. 515 с.
11. Таха Х. А. Введение в исследование операций. 6-е издание: пер. с англ. // М.: Издательский дом "Вильямс". 2001. 915 с.
12. Дудник Б. Я., Овчеренко В. Ф., Орлов В. К. и др. Надежность и живучесть систем связи / Под ред. Б. Я. Дудника // М.: Радио и связь. 1984. 216 с.
2. Кучерявый Е.А. Управление трафиком и качество обслуживания в сети Интернет // СПб.: Наука и Техника. 2004. 336 с.
3. Ford L.R., Fulkerson Jr. Fulkerson, D.R. Maximal Flow through a Network // Canadian Journal of Mathematics. 1956. pp. 399–404.
4. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 3-е издание // М.: "Вильямс". 2013. 1323 с.
5. Dinitz Y. Dinitz' Algorithm: The Original Version and Even's Version // Theoretical Computer Science: Essays in Memory of Shimon Even. Springer, 2006. pp. 218–240.
6. Arora S., Hazan E., Kale S. The multiplicative weights update method: A meta-algorithm and applications // Theory OF Computing. 2012. pp. 121–164.
7. Christiano P., Kelner J., Madry A., Spielman D., Teng S. Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs // Proceedings of the forty-third annual ACM symposium on Theory of computing (STOC 2011). 2011. pp. 273–282.
8. Lee Y.T., Rao S., Srivastava N. A new approach to computing maximum flows using electrical flows // Proceedings of the forty-fifth annual ACM symposium on Theory of computing (STOC 2013). 2013. pp. 755–764.
9. Кристофидес Н. Теория графов. Алгоритмический подход // М.: Мир. 1978. 432 с.
10. Нечепуренко М.И., Попков В.К., Майнагашев С.М. Алгоритмы и программы решения задач на графах и сетях // Новосибирск: Наука. Сиб. отделение. 1990. 515 с.
11. Таха Х. А. Введение в исследование операций. 6-е издание: пер. с англ. // М.: Издательский дом "Вильямс". 2001. 915 с.
12. Дудник Б. Я., Овчеренко В. Ф., Орлов В. К. и др. Надежность и живучесть систем связи / Под ред. Б. Я. Дудника // М.: Радио и связь. 1984. 216 с.
Опубликован
2014-11-11
Как цитировать
Трегубов, Р. Б., Лазарев, С. Н., & Андреев, С. Ю. (2014). Алгоритм нахождения k максимальных потоков. Труды СПИИРАН, 4(35), 33-48. https://doi.org/10.15622/sp.35.3
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
