|
Записки научных семинаров ПОМИ, 2002, том 293, страницы 129–138
(Mi znsl1679)
|
|
|
|
Эта публикация цитируется в 13 научных статьях (всего в 13 статьях)
Решение задачи о максимальном сечении за время $2^{|E|/4}$
А. С. Куликов, С. С. Федин Санкт-Петербургский государственный университет
Аннотация:
В данной работе мы приводим детерминированный алгоритм, находящий максимальное сечение в графе за время $\operatorname{poly}(|E|)\cdot 2^{|E|/4}$, где $|E|$ – количество ребер (между двумя вершинами могут быть кратные ребра). Эта оценка улучшает предыдущую известную оценку $\operatorname{poly}(|E|)\cdot 2^{|E|/3}$ Грамма и др. (2000). Библ. – 8 назв.
Поступило: 08.12.2002
Образец цитирования:
А. С. Куликов, С. С. Федин, “Решение задачи о максимальном сечении за время $2^{|E|/4}$”, Теория сложности вычислений. VII, Зап. научн. сем. ПОМИ, 293, ПОМИ, СПб., 2002, 129–138; J. Math. Sci. (N. Y.), 126:3 (2005), 1200–1204
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl1679 https://www.mathnet.ru/rus/znsl/v293/p129
|
Статистика просмотров: |
Страница аннотации: | 296 | PDF полного текста: | 151 |
|