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

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

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



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






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


Дискретн. анализ и исслед. опер., сер. 2, 2004, том 11, номер 1, страницы 11–25 (Mi da125)  

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

Приближенные алгоритмы для нахождения двух реберно непересекающихся гамильтоновых циклов минимального веса

А. Е. Бабурин, Э. Х. Гимади, Н. М. Коркишко

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

Аннотация: Рассматривается задача нахождения двух реберно непересекающихся гамильтоновых циклов минимального суммарного веса в полном неориентированном взвешенном графе, в котором для весов выполняется неравенство треугольника. Показано, что задача NP-трудна в сильном смысле. Предложены два приближенных алгоритма с временной сложностью $O(n^3)$ в случае, когда на ребрах графа задана одна весовая функция и когда заданы две весовые функции. Показано, что соответствующие оценки точности асимптотически (с ростом $n$) равны 9/4 и 12/5.

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

Реферативные базы данных:
УДК: 519.8
Статья поступила: 10.10.2003

Образец цитирования: А. Е. Бабурин, Э. Х. Гимади, Н. М. Коркишко, “Приближенные алгоритмы для нахождения двух реберно непересекающихся гамильтоновых циклов минимального веса”, Дискретн. анализ и исслед. опер., сер. 2, 11:1 (2004), 11–25

Цитирование в формате AMSBIB
\RBibitem{BabGimKor04}
\by А.~Е.~Бабурин, Э.~Х.~Гимади, Н.~М.~Коркишко
\paper Приближенные алгоритмы для нахождения двух реберно непересекающихся гамильтоновых циклов минимального веса
\jour Дискретн. анализ и исслед. опер., сер.~2
\yr 2004
\vol 11
\issue 1
\pages 11--25
\mathnet{http://mi.mathnet.ru/da125}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2084543}
\zmath{https://zbmath.org/?q=an:1045.05082}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da125
  • http://mi.mathnet.ru/rus/da/v11/s2/i1/p11

    ОТПРАВИТЬ: 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. Э. Х. Гимади, Ю. В. Глазков, “Об асимптотически точном алгоритме решения одной модификации трёхиндексной планарной задачи о назначениях”, Дискретн. анализ и исслед. опер., сер. 2, сер. 2, 13:1 (2006), 10–26  mathnet  mathscinet  zmath; E. Kh. Gimadi, Yu. V. Glazkov, “An asymptotically exact algorithm for one modification of planar three-index assignment”, J. Appl. Industr. Math., 1:4 (2007), 442–452  crossref
    2. А. А. Агеев, А. Е. Бабурин, Э. Х. Гимади, “Полиномиальный алгоритм с оценкой точности 3/4 для отыскания двух непересекающихся гамильтоновых циклов максимального веса”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 13:2 (2006), 11–20  mathnet  mathscinet  zmath; A. A. Ageev, A. E. Baburin, E. Kh. Gimadi, “A polynomial algorithm with an accuracy estimate of 3/4 for finding two nonintersecting Hamiltonian cycles of maximum weight”, J. Appl. Industr. Math., 1:2 (2007), 142–147  crossref
    3. Э. Х. Гимади, Ю. В. Глазков, А. Н. Глебов, “Алгоритмы приближённого решения задачи о двух коммивояжёрах в полном графе с весами рёбер 1 и 2”, Дискретн. анализ и исслед. опер., сер. 2, сер. 2, 14:2 (2007), 41–61  mathnet  zmath; J. Appl. Industr. Math., 3:1 (2009), 46–60  crossref
    4. Ageev A.A., Pyatkin A.V., “A 2-approximation algorithm for the metric 2-peripatetic salesman problem”, Approximation and Online Algorithms, Lecture Notes in Computer Science, 4927, 2008, 103–115  crossref  mathscinet  zmath  isi  scopus
    5. А. А. Агеев, А. В. Пяткин, “Приближённый алгоритм решения метрической задачи о двух коммивояжёрах с оценкой точности 2”, Дискретн. анализ и исслед. опер., 16:4 (2009), 3–20  mathnet  mathscinet  zmath
    6. Baburin A.E., Della Croce F., Gimadi E.K., Glazkov Y.V., Paschos V.T., “Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2”, Discrete Appl Math, 157:9 (2009), 1988–1992  crossref  mathscinet  zmath  isi  elib  scopus
    7. А. Е. Бабурин, Э. Х. Гимади, “Об асимптотической точности эффективного алгоритма решения задачи $m$-PSP на максимум в многомерном eвклидовом пространстве”, Тр. ИММ УрО РАН, 16, № 3, 2010, 12–24  mathnet  elib; A. E. Baburin, E. Kh. Gimadi, “On the asymptotic accuracy of an algorithm for solving the $m$-PSP maximum problem in a multidimensional Euclidean space”, Proc. Steklov Inst. Math. (Suppl.), 272, suppl. 1 (2011), S1–S13  crossref  isi
    8. А. Н. Глебов, А. В. Гордеева, Д. Ж. Замбалаева, “Алгоритм с оценкой 7/5 для задачи о двух коммивояжерах на минимум с различными весовыми функциями”, Сиб. электрон. матем. изв., 8 (2011), 296–309  mathnet
    9. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа”, Дискретн. анализ и исслед. опер., 20:5 (2013), 13–30  mathnet  mathscinet; E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, “On $m$-capacitated peripatetic salesman problem”, J. Appl. Industr. Math., 8:1 (2014), 40–52  crossref
    10. Shenmaier V.V., “Asymptotically Optimal Algorithms for Geometric Max Tsp and Max M-Psp”, Discrete Appl. Math., 163:2, SI (2014), 214–219  crossref  mathscinet  zmath  isi  elib  scopus
    11. Gimadi E.Kh. Glebov A.N. Skretneva A.A. Tsidulko O.Yu. Zambalaeva D.Zh., “Combinatorial Algorithms With Performance Guarantees For Finding Several Hamiltonian Circuits in a Complete Directed Weighted Graph”, Discrete Appl. Math., 196:SI (2015), 54–61  crossref  mathscinet  zmath  isi  elib  scopus
    12. Э. Х. Гимади, О. Ю. Цидулко, “Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением”, Дискретн. анализ и исслед. опер., 24:3 (2017), 5–19  mathnet  crossref  elib; E. Kh. Gimadi, O. Yu. Tsidulko, “An asymptotically optimal algorithm for the $m$-peripatetic salesman problem on random inputs with discrete distribution”, J. Appl. Industr. Math., 11:3 (2017), 354–361  crossref
    13. А. Н. Глебов, С. Г. Токтохоева, “Полиномиальный $3/5$-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 26:2 (2019), 30–59  mathnet  crossref; A. N. Glebov, S. G. Toktokhoeva, “A polynomial $3/5$-approximate algorithm for the asymmetric maximization version of $3$-PSP”, J. Appl. Industr. Math., 13:2 (2019), 219–238  crossref
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:518
    Полный текст:130
    Литература:42
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020