• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Семинар по алгоритмам и структурам данных

Семинар по алгоритмам и структурам данных ФКН создан для всех, кто интересуется последними достижениями данной дисциплины или ищет актуальные задачи для своей научной деятельности. Доклады доступны широкому кругу слушателей, включая аспирантов и заинтересованных студентов.

Заседания проходят по вторникам с 18:10 до 19:30, ориентировочно раз в месяц (следите за объявлениями). 

 

Организатор семинара: Мамай Игорь Борисович, доцент департамента больших данных и информационного поиска ФКН

 

 

14 октября 2025 в 18:10

Докладчик: Никита Мануйленко, ФКН НИУ ВШЭ

Тема: Полиномиальный алгоритм распознавания точной степени 3 графов-деревьев.

Аннотация: Вопрос степеней графов изучается с 1960-го года. Степень n графа G — это граф G’ на том же множестве вершин, где между парой вершин есть ребро тогда и только тогда, когда длина пути между этими вершинами в G не превосходит n. Доказано, что распознавание, является ли данный граф степенью 2 какого-то графа — NP-полная задача, и может быть решена за полиномиальное время только для некоторых подклассов графов.
Вопрос точной степени n графа G очень похож, но здесь мы ограничиваемся ребрами в графе G’ тогда, когда между соответствующей парой вершин в графе G существует простой путь длины n. Доказано, что возможно за полиномиальное время определить, является ли граф точной степенью 2 какого-то графа. В нашей работе нам удалось доказать, что задача распознавания, является ли граф точной степенью 3 графа-дерева, также является полиномиально разрешимой.


Место проведения: Покровский бульвар 11, аудитория D109.

Регистрация

2025

8) 10 июня, Юрий Дементьев: Алгоритмы справедливых дележей неделимых предметов

7) 18 марта, Игорь Мамай: Статическая оптимальность и другие свойства Splay-дерева

6) 17 декабря, Игорь Мамай: Вероятностная структура данных Zip-дерево

2024

5) 19 ноября, Филипп Грибов: Алгоритм Торупа для поиска кратчайшего расстояния во взвешенном графе за линейное время

4) 3 октября, Никита Звонков: Поиск минимального объединения остовных деревьев в графе со случайными весами рёбер

3) 14 мая, Филипп Рухович: Внешние биллиарды вне правильных многоугольников

2) 23 апреля, Филипп Грибов: Понижение оценки 𝛀(log n) на время выполнения основных операций с упорядоченным множеством при работе с целыми числами

1) 5 марта, Иван Смрнов: Точные оценки сортировок и распределённый перебор алгоритмов