Loading [MathJax]/jax/output/SVG/config.js
Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Дискретный анализ и исследование операций, 2015, том 22, выпуск 4, страницы 5–20
DOI: https://doi.org/10.17377/daio.2015.22.474 (Mi da821) 		 
Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)

Вероятностный анализ алгоритма нахождения в графе минимального остовного дерева с ограниченным снизу диаметром

Э. Х. Гимадиab, Е. Ю. Шинb

a Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия
b Институт математики им. С. Л. Соболева, пр. Коптюга, 4, 630090 Новосибирск, Россия
PDF полного текста (271 kB) Список цитирования (7)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.17377/daio.2015.22.474
Аннотация: Рассматриваются графы с классом матриц, элементы которых – веса рёбер – выбираются случайно и независимо из неограниченного сверху интервала с непрерывной функцией распределения. Проведён вероятностный анализ приближённого алгоритма с квадратичной временно́й сложностью в случае экспоненциального распределения. Обоснованы достаточные условия асимптотической точности алгоритма. Аналогичные условия получены также в случае усечённо-нормального распределения. Ил. 2, библиогр. 17.
Ключевые слова: остовное дерево, полиномиальный алгоритм, вероятностный анализ, оценки качества алгоритма, асимптотическая точность.
Статья поступила: 10.02.2015
Переработанный вариант: 04.05.2015
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2015, Volume 9, Issue 4, Pages 480–488
DOI: https://doi.org/10.1134/S1990478915040043
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.8
Образец цитирования: Э. Х. Гимади, Е. Ю. Шин, “Вероятностный анализ алгоритма нахождения в графе минимального остовного дерева с ограниченным снизу диаметром”, Дискретн. анализ и исслед. опер., 22:4 (2015), 5–20; J. Appl. Industr. Math., 9:4 (2015), 480–488
Цитирование в формате AMSBIB
\RBibitem{GimShi15}
\by Э.~Х.~Гимади, Е.~Ю.~Шин
\paper Вероятностный анализ алгоритма нахождения в~графе минимального остовного дерева с~ограниченным снизу диаметром
\jour Дискретн. анализ и исслед. опер.
\yr 2015
\vol 22
\issue 4
\pages 5--20
\mathnet{http://mi.mathnet.ru/da821}
\crossref{https://doi.org/10.17377/daio.2015.22.474}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3467232}
\elib{https://elibrary.ru/item.asp?id=23859894}
\transl
\jour J. Appl. Industr. Math.
\yr 2015
\vol 9
\issue 4
\pages 480--488
\crossref{https://doi.org/10.1134/S1990478915040043}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da821
  • https://www.mathnet.ru/rus/da/v22/i4/p5
    • Эта публикация цитируется в следующих 7 статьяx:
    1. Э. Х. Гимади, А. А. Штепа, “Об асимптотической точности поиска минимума суммы весов разнореберных остовных деревьев фиксированного диаметра”, Автомат. и телемех., 2023, № 7, 146–166  mathnet  crossref; E. Kh. Gimadi, A. A. Shtepa, “On asymptotically optimal approach for finding of the minimum total weight of edge-disjoint spanning trees with a given diameter”, Autom. Remote Control, 84:7 (2023), 872–888  crossref
    2. E. Kh. Gimadi, A. A. Shtepa, “On Asymptotically Optimal Approach for Finding of the Minimum Total Weight of Edge-Disjoint Spanning Trees with a Given Diameter”, Autom Remote Control, 84:7 (2023), 772  crossref
    3. Edward Kh. Gimadi, Aleksandr S. Shevyakov, Alexandr A. Shtepa, Lecture Notes in Computer Science, 12755, Mathematical Optimization Theory and Operations Research, 2021, 67  crossref
    4. Edward K. Gimadi, Aleksandr S. Shevyakov, Alexandr A. Shtepa, Lecture Notes in Computer Science, 12422, Optimization and Applications, 2020, 110  crossref
    5. E. Gimadi, A. Shevyakov, E. Shin, “Asymptotically optimal approach to a given diameter undirected MST problem on random input data”, 2019 15Th International Asian School-Seminar Optimization Problems of Complex Systems (OPCS 2019), IEEE, 2019, 48–52  isi
    6. Edward Kh. Gimadi, Ekaterina Yu. Shin, Communications in Computer and Information Science, 1090, Mathematical Optimization Theory and Operations Research, 2019, 30  crossref
    7. Edward Gimadi, Alexandr Shevyakov, Ekaterina Shin, 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems (OPCS), 2019, 48  crossref
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:385
    PDF полного текста:131
    Список литературы:58
    Первая страница:14
     
      Обратная связь:
    math-net2025_04@mi-ras.ru     		 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025