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

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

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



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






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


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

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

Полиномиальный алгоритм с оценкой точности 3/4 для отыскания двух непересекающихся гамильтоновых циклов максимального веса

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

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

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

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2007, 1:2, 142–147

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


Образец цитирования: А. А. Агеев, А. Е. Бабурин, Э. Х. Гимади, “Полиномиальный алгоритм с оценкой точности 3/4 для отыскания двух непересекающихся гамильтоновых циклов максимального веса”, Дискретн. анализ и исслед. опер., сер. 1, 13:2 (2006), 11–20; J. Appl. Industr. Math., 1:2 (2007), 142–147

Цитирование в формате AMSBIB
\RBibitem{AgeBabGim06}
\by А.~А.~Агеев, А.~Е.~Бабурин, Э.~Х.~Гимади
\paper Полиномиальный алгоритм с~оценкой точности~3/4 для отыскания двух непересекающихся гамильтоновых циклов максимального веса
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2006
\vol 13
\issue 2
\pages 11--20
\mathnet{http://mi.mathnet.ru/da28}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2289335}
\zmath{https://zbmath.org/?q=an:1249.05232}
\transl
\jour J. Appl. Industr. Math.
\yr 2007
\vol 1
\issue 2
\pages 142--147
\crossref{https://doi.org/10.1134/S1990478907020020}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-34447100592}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da28
  • http://mi.mathnet.ru/rus/da/v13/s1/i2/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. Э. Х. Гимади, Ю. В. Глазков, А. Н. Глебов, “Алгоритмы приближённого решения задачи о двух коммивояжёрах в полном графе с весами рёбер 1 и 2”, Дискретн. анализ и исслед. опер., сер. 2, сер. 2, 14:2 (2007), 41–61  mathnet  zmath; J. Appl. Industr. Math., 3:1 (2009), 46–60  crossref
    2. 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
    3. А. А. Агеев, А. В. Пяткин, “Приближённый алгоритм решения метрической задачи о двух коммивояжёрах с оценкой точности 2”, Дискретн. анализ и исслед. опер., 16:4 (2009), 3–20  mathnet  mathscinet  zmath
    4. 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
    5. А. Е. Бабурин, Э. Х. Гимади, “Об асимптотической точности эффективного алгоритма решения задачи $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
    6. А. Н. Глебов, Д. Ж. Замбалаева, “Полиномиальный алгоритм с оценкой точности $7/9$ для задачи о двух коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 18:4 (2011), 17–48  mathnet  mathscinet  zmath; A. N. Glebov, D. Zh. Zambalayeva, “Polynomial algorithm with approximation ratio $7/9$ for maximum 2-PSP”, J. Appl. Industr. Math., 6:1 (2012), 69–89  crossref
    7. А. Н. Глебов, Д. Ж. Замбалаева, “Приближённый алгоритм решения задачи о двух коммивояжёрах на минимум с различными весовыми функциями”, Дискретн. анализ и исслед. опер., 18:5 (2011), 11–37  mathnet  mathscinet  zmath; A. N. Glebov, D. Zh. Zambalayeva, “An approximation algorithm for the minimum 2-PSP with different weight functions valued 1 and 2”, J. Appl. Industr. Math., 6:2 (2012), 167–183  crossref
    8. А. Н. Глебов, А. В. Гордеева, Д. Ж. Замбалаева, “Алгоритм с оценкой 7/5 для задачи о двух коммивояжерах на минимум с различными весовыми функциями”, Сиб. электрон. матем. изв., 8 (2011), 296–309  mathnet
    9. Э. Х. Гимади, Е. В. Ивонина, “Приближённые алгоритмы решения задачи о двух коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 19:1 (2012), 17–32  mathnet  mathscinet; E. Kh. Gimadi, E. V. Ivonina, “Approximation algorithms for maximum-weight problem of two-peripatetic salesmen”, J. Appl. Industr. Math., 6:3 (2012), 295–305  crossref
    10. Duchenne E., Laporte G., Semet F., “The Undirected M-Capacitated Peripatetic Salesman Problem”, Eur. J. Oper. Res., 223:3 (2012), 637–643  crossref  mathscinet  zmath  isi  elib  scopus
    11. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа”, Дискретн. анализ и исслед. опер., 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
    12. 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
    13. Michallet J., Prins Ch., Amodeo L., Yalaoui F., Vitry G., “Multi-Start Iterated Local Search for the Periodic Vehicle Routing Problem with Time Windows and Time Spread Constraints on Services”, Comput. Oper. Res., 41 (2014), 196–207  crossref  mathscinet  zmath  isi  elib  scopus
    14. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “Задача о двух коммивояжерах с ограничениями на пропускные способности ребер графа с различными весовыми функциями”, Вестн. НГУ. Сер. матем., мех., информ., 14:3 (2014), 3–18  mathnet
    15. 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
    16. Э. Х. Гимади, О. Ю. Цидулко, “Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением”, Дискретн. анализ и исслед. опер., 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
    17. Gimadi E.Kh., Tsidulko O.Yu., “Approximation Algorithms For the Maximum M-Peripatetic Salesman Problem”, Analysis of Images, Social Networks and Texts, Aist 2017, Lecture Notes in Computer Science, 10716, eds. VanDerAalst W., Ignatov D., Khachay M., Kuznetsov S., Lempitsky V., Lomazova I., Loukachevitch N., Napoli A., Panchenko A., Pardalos P., Savchenko A., Wasserman S., Springer International Publishing Ag, 2018, 304–312  crossref  mathscinet  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:483
    Полный текст:131
    Литература:39
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019