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

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

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



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






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


Дискретн. анализ и исслед. опер., сер. 2, 2006, том 13, номер 2, страницы 3–20 (Mi da2)  

Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

Приближенный алгоритм поиска $d$-однородного связного остовного подграфа максимального веса в полном графе со случайными весами ребер

А. Е. Бабурин, Э. Х. Гимади

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Предложен приближeнный полиномиальный алгоритм для решения задачи поиска $d$-однородного связного остовного подграфа максимального веса в полном неориентированном взвешенном $n$-вершинном графе. Проведeн вероятностный анализ алгоритма для решения задачи со случайными входными данными (весами рeбер) в случае равномерного распределения весов рeбер и в случае распределений минорирующего типа. Показано, что предложенный алгоритм временно́й сложности $O(n^2+nd\ln n)$ находит асимптотически точное решение задачи при $d=o(n)$. В случае $d\leqslant n\ln n$ асимптотически точное решение может быть получено с временной сложностью $O(n^2)$. Для минимизационной версии задачи к условию асимптотической точности модифицированного алгоритма добавляется дополнительное ограничение на величину разброса значений весов рeбер графа.
Библ. 6.

Полный текст: PDF файл (289 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2008, 2:2, 155–166

Реферативные базы данных:


Образец цитирования: А. Е. Бабурин, Э. Х. Гимади, “Приближенный алгоритм поиска $d$-однородного связного остовного подграфа максимального веса в полном графе со случайными весами ребер”, Дискретн. анализ и исслед. опер., сер. 2, 13:2 (2006), 3–20; J. Appl. Industr. Math., 2:2 (2008), 155–166

Цитирование в формате AMSBIB
\RBibitem{BabGim06}
\by А.~Е.~Бабурин, Э.~Х.~Гимади
\paper Приближенный алгоритм поиска $d$-однородного связного остовного подграфа максимального веса в~полном графе со случайными весами ребер
\jour Дискретн. анализ и исслед. опер., сер.~2
\yr 2006
\vol 13
\issue 2
\pages 3--20
\mathnet{http://mi.mathnet.ru/da2}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2310924}
\zmath{https://zbmath.org/?q=an:1249.90210}
\transl
\jour J. Appl. Industr. Math.
\yr 2008
\vol 2
\issue 2
\pages 155--166
\crossref{https://doi.org/10.1134/S1990478908020026}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-44849132851}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da2
  • http://mi.mathnet.ru/rus/da/v13/s2/i2/p3

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Э. Х. Гимади, “О вероятностном анализе приближённого алгоритма решения задачи о $p$-медиане”, Дискретн. анализ и исслед. опер., 17:3 (2010), 19–31  mathnet  mathscinet  zmath
    2. Э. Х. Гимади, В. Т. Дементьев, “Вероятностный анализ децентрализованной версии одного обобщения задачи о назначениях”, Дискретн. анализ и исслед. опер., 18:3 (2011), 11–20  mathnet  mathscinet  zmath
    3. Э. Х. Гимади, А. В. Шахшнейдер, “Приближенные алгоритмы с оценками для задач маршрутизации на случайных входах с ограниченным числом клиентов в каждом маршруте”, Автомат. и телемех., 2012, № 2, 126–140  mathnet; E. Kh. Gimadi, A. V. Shakhshneyder, “Approximate algorithms with estimates for routing problems on random inputs with a bounded number of customers per route”, Autom. Remote Control, 73:2 (2012), 323–335  crossref  isi
    4. Cornelissen K., Hoeksma R., Manthey B., Narayanaswamy N.S., Rahul C.S., “Approximability of Connected Factors”, Approximation and Online Algorithms, Waoa 2013, Lecture Notes in Computer Science, 8447, eds. Kaklamanis C., Pruhs K., Springer-Verlag Berlin, 2014, 120–131  crossref  mathscinet  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:339
    Полный текст:82
    Литература:22
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019