RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары






Узлы и теория представлений
31 мая 2011 г. 18:30, г. Москва, ГЗ МГУ, ауд. 14-03
 


О реберной планаризации и crossing number графов

Ю. С. Макарычев

Toyota Technological Institute at Chicago

Количество просмотров:
Эта страница:90

Аннотация: Мой доклад будет посвящён задаче нахождения «оптимального» вложения графа в плоскость, т.е. вложения с минимальным числом скрещиваний (числом пересекающихся рёбер). Сначала я кратко изложу известные результаты. В частности, я покажу, что задачу нельзя решить точно за полиномиальное время (если $P$ не равно $NP$) [Garey and Johnson 1983]. Затем мы обсудим приближённые методы её решения. Я расскажу о связи этой задачи с задачей о «рёберной планаризации» и опишу новые аппроксимационные алгоритмы для неё.
Доклад основан на совместной работе с Julia Chuzhoy и Anastasios Sidiropoulos.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021