ИСТИНА |
Войти в систему Регистрация |
|
ФНКЦ РР |
||
Доклад посвящен алгоритмическому подходу Карпа-Сипсера для оценки числа независимости случайных графов и гиперграфов. Данный подход оказывается наиболее эффективен в разреженном случае, когда каждая вершина в среднем имеет константную степень. Несложно понять, что в подобной модели число независимости обязано быть линейным по числу вершин.