Автоматика и телемеханика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов
Загрузить рукопись

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

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


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




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

Автоматика и телемеханика, 2023, выпуск 7, страницы 146–166
DOI: https://doi.org/10.31857/S0005231023070085 (Mi at16118) 		 
Оптимизация, системный анализ и исследование операций

Об асимптотической точности поиска минимума суммы весов разнореберных остовных деревьев фиксированного диаметра

Э. Х. Гимадиa, А. А. Штепаb

a Институт математики им. С.Л. Соболева СО РАН, Новосибирск
b Новосибирский национальный исследовательский государственный университет
PDF полного текста (620 kB) Первая страница
Список литературы:
PDF
HTML
DOI: https://doi.org/10.31857/S0005231023070085
Аннотация: Рассматривается труднорешаемая задача поиска нескольких реберно-непересекающихся (разнореберных) остовных деревьев минимального суммарного веса с фиксированным диаметром в полном неориентированном графе со случайными весами ребер из нескольких классов непрерывных распределений: равномерное, смещенное усеченно-экспоненциальное, смещенное усеченно-нормальное. Для решения этой задачи предлагается приближенный алгоритм с трудоемкостью $O(n^2)$, где $n$ — количество вершин в графе. Приводятся условия асимптотической точности для этого алгоритма в случае каждого из рассматриваемых вероятностных распределений.
Ключевые слова: минимальное остовное дерево с ограниченным диаметром, приближенный алгоритм, вероятностный анализ, асимптотическая точность.
Финансовая поддержка Номер гранта
Министерство науки и высшего образования Российской Федерации FWNF-2022-001
Работа выполнена в рамках государственного задания Института математики им. С.Л. Соболева СО РАН (проект FWNF-2022-0019).
Статья представлена к публикации членом редколлегии: А. А. Лазарев

Поступила в редакцию: 23.01.2023
После доработки: 27.03.2023
Принята к публикации: 28.04.2023
Англоязычная версия:
Automation and Remote Control, 2023, Volume 84, Issue 7, Pages 872–888
DOI: https://doi.org/10.25728/arcRAS.2023.42.85.001
Реферативные базы данных:
Тип публикации: Статья
Образец цитирования: Э. Х. Гимади, А. А. Штепа, “Об асимптотической точности поиска минимума суммы весов разнореберных остовных деревьев фиксированного диаметра”, Автомат. и телемех., 2023, № 7, 146–166; Autom. Remote Control, 84:7 (2023), 872–888
Цитирование в формате AMSBIB
\RBibitem{GimSht23}
\by Э.~Х.~Гимади, А.~А.~Штепа
\paper Об асимптотической точности поиска минимума суммы весов разнореберных остовных деревьев фиксированного диаметра
\jour Автомат. и телемех.
\yr 2023
\issue 7
\pages 146--166
\mathnet{http://mi.mathnet.ru/at16118}
\crossref{https://doi.org/10.31857/S0005231023070085}
\edn{https://elibrary.ru/FDWYOE}
\transl
\jour Autom. Remote Control
\yr 2023
\vol 84
\issue 7
\pages 872--888
\crossref{https://doi.org/10.25728/arcRAS.2023.42.85.001}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/at16118
  • https://www.mathnet.ru/rus/at/y2023/i7/p146
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Автоматика и телемеханика
    Статистика просмотров:
    Страница аннотации:79
    Список литературы:21
    Первая страница:9
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024