Том 22, номер 4, 2015 г., Стр. 5–20

УДК 519.8
Гимади Э. Х., Шин Е. Ю.
Вероятностный анализ алгоритма нахождения в графе минимального остовного дерева с ограниченным снизу диаметром

Аннотация:
Рассматриваются графы с классом матриц, элементы которых — веса рёбер — выбираются случайно и независимо из неограниченного сверху интервала с непрерывной функцией распределения. Проведён вероятностный анализ приближённого алгоритма с квадратичной временной сложностью в случае экспоненциального распределения. Обоснованы достаточные условия асимптотической точности алгоритма. Аналогичные условия получены также в случае усечённо-нормального распределения.
Ил. 2, библиогр. 17.

Ключевые слова: остовное дерево, полиномиальный алгоритм, вероятностный анализ, оценки качества алгоритма, асимптотическая точность.

DOI: 10.17377/daio.2015.22.474

Гимади Эдуард Хайрутдинович ^1,2
Шин Екатерина Юрьевна ¹
1. Институт математики им. С. Л. Соболева
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет
ул. Пирогова, 2, 630090 Новосибирск, Россия
e-mail: gimadi@math.nsc.ru, Shinus90@yandex.ru

Статья поступила 10 февраля 2015 г.
Исправленный вариант — 4 мая 2015 г.

Литература

[1] Гимади Э. Х., Глазков Ю. В. Об асимптотически точном алгоритме решения одной модификации трёхиндексной планарной задачи о назначениях // Дискрет. анализ и исслед. операций. Сер. 2. 2006. Т. 13, № 1. С. 10–26.

[2] Гимади Э. Х., ЛеГаллу А., Шахшнейдер А. В. Вероятностный анализ одного алгоритма приближённого решения задачи коммивояжёра на неограниченных сверху входных данных // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 1. С. 23–43.

[3] Гимади Э. Х., Перепелица В. А. Асимптотический подход к решению задачи коммивояжёра // Управляемые системы. Сб. науч. тр. Вып. 12. Новосибирск: Ин-т математики СО АН СССР, 1974. С. 35–45.

[4] Гимади Э. Х., Сердюков А. И. Об одном алгоритме нахождения минимального остова с ограниченным снизу диаметром // Дискрет. анализ и исслед. операций. Сер. 1. 2000. Т. 7, № 2. С. 3–11.

[5] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М: Мир, 1982. 416 с.

[6] Перепелица В. А., Гимади Э. Х. Задача нахождения минимального гамильтонова цикла в взвешенном графе // Дискрет. анализ. Сб. науч. тр. Вып. 15. Новосибирск: Ин-т математики СО АН СССР, 1969. С. 57–65.

[7] Петров В. В. Предельные теоремы для сумм независимых случайных величин. М.: Наука, 1987. 317 с.

[8] Прим Р. К. Кратчайшие связывающие сети и некоторые обобщения // Кибернетический сборник. Вып. 2. М.: Мир, 1961. С. 95–107.

[9] Abdalla A., Deo N., Gupta P. Random-tree diameter and the diameter constrained MST // Congr. Numerantium. 2000. Vol. 144. P. 161–182.

[10] Bertsimas D. J. The probabilistic minimum spanning tree problem // Networks. 1990. Vol. 20, No. 3. P. 245–275.

[11] Gruber M., Raidl G. R. A new 0–1 ILP approach for the bounded-diameter minimum spanning tree problem // Proc. 2nd Int. Network Optimization Conf. (Lisbon, Portugal, March 20–23, 2005). 2005. Vol. 1. P. 178–185.

[12] Johnson D. S., Lenstra J. K., Rinnooy Kan A. H. G. The complexity of the network design problem // Networks. 1978. Vol. 8, No. 4. P. 279–285.

[13] Julstrom B. A. Greedy heuristics for the bounded-diameter minimum spanning tree problem // J. Exp. Algorithmics. 2009. No. 14. P. 1–14.

[14] Julstrom B. A., Raidl G. R. A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem // Genet. Evol. Comput. Conference’s Workshops Proc., Workshop Anal. Des. Represent. Operat., Chicago, USA, July 12–16, 2003, pp. 2–7, 2003. Available at https://www.ac.tuwien.ac.at/files/pub/julstrom-03.pdf. Accessed June 11, 2015.

[15] Ozeki K., Yamashita T. Spanning trees: A survey // Graphs Comb. 2011. Vol. 27, No. 1. P. 1–26.

[16] Raidl G. R., Julstrom B. A. Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem // Proc. 2003 ACM Symp. Applied Computing (Melbourne, FL, March 9–12, 2003). New York: ACM Press, 2003. P. 747–752.

[17] Jothi R., Raghavachari B. Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design // ACM Trans. Algorithms. 2005. Vol. 1, No. 2. P. 265–282.