К нахождению радиуса устойчивости минимального остовного дерева

  • Евгений Дмитриевич Живица Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск
  • Кирилл Геннадьевич Кузьмин Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск

Аннотация

Рассмотрена задача о нахождении минимального остовного дерева при условии, что вес ребер подвержен независимым изменениям. Изучена одна из количественных характеристик устойчивости оптимальных решений этой задачи, известная как радиус устойчивости и определяемая как предельный уровень изменений веса ребер, при котором выбранное наперед оптимальное решение все еще сохраняет свою оптимальность. Выведена точная формула радиуса устойчивости минимального остовного дерева, позволяющая вычислять этот радиус за время, близкое к линейному относительно числа ребер графа. Этот результат значительно улучшает формулу радиуса устойчивости оптимального решения линейной комбинаторной задачи в общей постановке, поскольку последняя формула требует полного перебора по множеству допустимых решений, мощность которого может расти экспоненциально.

Биографии авторов

Евгений Дмитриевич Живица, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск

магистрант кафедры математической кибернетики механико-математического факультета. Научный руководитель – К. Г. Кузьмин

Кирилл Геннадьевич Кузьмин, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск

кандидат физико-математических наук, доцент; доцент кафедры математической кибернетики механико-математического факультета

Литература

  1. Gordeev Je. N. Issledovanie ustojchivosti zadachi o kratchajshem ostovnom dereve v metrike l1 [Stability analysis of the minimum spanning tree problem]. Zh. vychislitel. mat. mat. fiz. 1999. Vol. 39, No. 5. P. 770 –778 (in Russ.).
  2. Sergienko I. V., Shilo V. P. Zadachi diskretnoj optimizacii. Problemy, metody reshenija, issledovanija [Discrete Optimization Problems. Challenges, Solution Techniques, and Analysis]. Kiev, 2003 (in Russ.).
  3. Emelichev V., Podkopaev D. Quantitative stability analysis for vector problems of 0 –1 programming. Discret. Optim. 2010. Vol. 7, No. 1/2. P. 48 – 63.
  4. Roland J., Smet Y. De, Figueira J. R. On the calculation of stability radius for multi-objective combinatorial optimization problems by inverse optimization. 4OR. 2012. Vol. 10, No. 4. P. 379 –389.
  5. Kuzʼmin K. G. Edinyj podhod k nahozhdeniju radiusov ustojchivosti v mnogokriterialʼnoj zadache o maksimalʼnom razreze grafa [A general approach to the calculation of stability radii for the max-cut problem with multiple criteria]. Diskretn. anal. issled. oper. 2015. Vol. 22, No. 5. P. 30 –51 (in Russ.).
  6. Eppstein D. Finding the k smallest spanning trees. BIT Numer. Math. 1992. Vol. 32, No. 2. P. 237–248.
  7. Frederickson G. N. Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and Smallest Spanning Trees Time. SIAM J. Comput. 1997. Vol. 26, No. 2. P. 484 –538.
  8. Pettie S. Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time. J. Graph Algorithms Appl. 2015. Vol. 19, No. 1. P. 375–391.
Опубликован
2017-12-03
Ключевые слова: задача о минимальном остовном дереве, второй оптимальный остов, анализ чувствительности решений, радиус устойчивости
Как цитировать
Живица, Е. Д., & Кузьмин, К. Г. (2017). К нахождению радиуса устойчивости минимального остовного дерева. Журнал Белорусского государственного университета. Математика. Информатика, 1, 34-38. Доступно по https://journals.bsu.by/index.php/mathematics/article/view/735
Выпуск
№ 1 (2017): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Дискретная математика и математическая кибернетика

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).