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

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

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


Тр. ИММ УрО РАН:
Год:
Том:
Выпуск:
Страница:
Найти




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

Труды Института математики и механики УрО РАН, 2013, том 19, номер 2, страницы 134–143 (Mi timm939)  
Эта публикация цитируется в 5 научных статьях (всего в 6 статьях)

2-приближенный алгоритм поиска клики с минимальным весом вершин и ребер

И. И. Ереминa, Э. Х. Гимадиb, А. В. Кельмановb, А. В. Пяткинb, М. Ю. Хачайac

a Институт математики и механики УрО РАН
b Институт математики СО РАН
c Уральский федеральный университет
PDF полного текста (182 kB) Список цитирования (6)
Список литературы:
PDF
HTML
Аннотация: Рассматривается задача о минимальной клике (относительно суммарного веса входящих в нее вершин и ребер) заданного размера в полном неориентированном взвешенном графе, а также некоторые из ее важных частных случаев. Анализируются вопросы аппроксимируемости. Для общего случая установлена слабая аппроксимируемость задачи. Предложен 2-приближенный эффективный алгоритм с временной сложностью O(n2) для случаев, когда веса вершин неотрицательны, а веса ребер либо удовлетворяют неравенству треугольника, либо являются квадратами попарных расстояний в некоторой системе точек евклидова пространства.
Ключевые слова: полный неориентированный граф, клика фиксированного размера, минимальный вес вершин и ребер, поиск подмножества, аппроксимируемость, полиномиальный приближенный алгоритм, оценка точности, временная сложность.
Поступила в редакцию: 10.02.2013
Англоязычная версия:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2014, Volume 284, Issue 1, Pages 87–95
DOI: https://doi.org/10.1134/S0081543814020084
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.16+519.85
Образец цитирования: И. И. Еремин, Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “2-приближенный алгоритм поиска клики с минимальным весом вершин и ребер”, Тр. ИММ УрО РАН, 19, № 2, 2013, 134–143; Proc. Steklov Inst. Math. (Suppl.), 284, suppl. 1 (2014), 87–95
Цитирование в формате AMSBIB
\RBibitem{EreGimKel13}
\by И.~И.~Еремин, Э.~Х.~Гимади, А.~В.~Кельманов, А.~В.~Пяткин, М.~Ю.~Хачай
\paper $2$-приближенный алгоритм поиска клики с~минимальным весом вершин и ребер
\serial Тр. ИММ УрО РАН
\yr 2013
\vol 19
\issue 2
\pages 134--143
\mathnet{http://mi.mathnet.ru/timm939}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3363380}
\elib{https://elibrary.ru/item.asp?id=19053975}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2014
\vol 284
\issue , suppl. 1
\pages 87--95
\crossref{https://doi.org/10.1134/S0081543814020084}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000334277400008}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84898742572}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/timm939
  • https://www.mathnet.ru/rus/timm/v19/i2/p134
    • Эта публикация цитируется в следующих 6 статьяx:
    1. Gennady G. Zabudsky, Natalia S. Veremchuk, Communications in Computer and Information Science, 1090, Mathematical Optimization Theory and Operations Research, 2019, 131  crossref
    2. Bianca Camille Silmaro, Geoffrey A. Solano, 2019 10th International Conference on Information, Intelligence, Systems and Applications (IISA), 2019, 1  crossref
    3. А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 55:2 (2015), 335–344  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors”, Comput. Math. Math. Phys., 55:2 (2015), 330–339  crossref  isi  elib
    4. А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 22:4 (2015), 50–62  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a bi-partitioning problem”, J. Appl. Industr. Math., 9:4 (2015), 497–502  crossref
    5. В. И. Бердышев, В. В. Васин, С. В. Матвеев, А. А. Махнев, Ю. Н. Субботин, Н. Н. Субботина, В. Н. Ушаков, М. Ю. Хачай, А. Г. Ченцов, “Иван Иванович Еремин”, Тр. ИММ УрО РАН, 20, № 2, 2014, 5–12  mathnet  mathscinet  elib; V. I. Berdyshev, V. V. Vasin, S. V. Matveev, A. A. Makhnev, Yu. N. Subbotin, N. N. Subbotina, V. N. Ushakov, M. Yu. Khachai, A. G. Chentsov, “Ivan Ivanovich Eremin”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 1–8  crossref  isi
    6. Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе”, Тр. ИММ УрО РАН, 20, № 2, 2014, 99–112  mathnet  mathscinet  elib; E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “Efficient algorithms with performance estimates for some problems of finding several cliques in a complete undirected weighted graph”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 88–101  crossref  isi
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Труды Института математики и механики УрО РАН
    Статистика просмотров:
    Страница аннотации:509
    PDF полного текста:123
    Список литературы:71
    Первая страница:4
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025