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

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

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


Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти




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

Записки научных семинаров ПОМИ, 2002, том 293, страницы 129–138 (Mi znsl1679)  
Эта публикация цитируется в 13 научных статьях (всего в 13 статьях)

Решение задачи о максимальном сечении за время $2^{|E|/4}$

А. С. Куликов, С. С. Федин

Санкт-Петербургский государственный университет
PDF полного текста (194 kB) Список цитирования (13)
Аннотация: В данной работе мы приводим детерминированный алгоритм, находящий максимальное сечение в графе за время $\operatorname{poly}(|E|)\cdot 2^{|E|/4}$, где $|E|$ – количество ребер (между двумя вершинами могут быть кратные ребра). Эта оценка улучшает предыдущую известную оценку $\operatorname{poly}(|E|)\cdot 2^{|E|/3}$ Грамма и др. (2000). Библ. – 8 назв.
Поступило: 08.12.2002
Англоязычная версия:
Journal of Mathematical Sciences (New York), 2005, Volume 126, Issue 3, Pages 1200–1204
DOI: https://doi.org/10.1007/s10958-005-0101-7
Реферативные базы данных:
УДК: 519.178+510.52
Образец цитирования: А. С. Куликов, С. С. Федин, “Решение задачи о максимальном сечении за время $2^{|E|/4}$”, Теория сложности вычислений. VII, Зап. научн. сем. ПОМИ, 293, ПОМИ, СПб., 2002, 129–138; J. Math. Sci. (N. Y.), 126:3 (2005), 1200–1204
Цитирование в формате AMSBIB
\RBibitem{KulFed02}
\by А.~С.~Куликов, С.~С.~Федин
\paper Решение задачи о~максимальном сечении за время $2^{|E|/4}$
\inbook Теория сложности вычислений.~VII
\serial Зап. научн. сем. ПОМИ
\yr 2002
\vol 293
\pages 129--138
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl1679}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1948828}
\zmath{https://zbmath.org/?q=an:1093.90070}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2005
\vol 126
\issue 3
\pages 1200--1204
\crossref{https://doi.org/10.1007/s10958-005-0101-7}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/znsl1679
  • https://www.mathnet.ru/rus/znsl/v293/p129
    • Эта публикация цитируется в следующих 13 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Записки научных семинаров ПОМИ
    Статистика просмотров:
    Страница аннотации:277
    PDF полного текста:138
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024