Среда, 28.10.2020, 05:15
Информатика и ИКТ
Приветствую Вас Гость | RSS
Главная Регистрация Вход
Меню сайта

Yandex_tech

Хабр-news

mail_news

Rambler

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

oszone.net

IT-N-образование

Главная » 2020 » Октябрь » 13 » Новый алгоритм проверки пересечений в графах прятался на виду
19:24
Новый алгоритм проверки пересечений в графах прятался на виду

Новый алгоритм проверки пересечений в графах прятался на виду

В октябре 2019 Якоб Хольм и Ева Ротенберг пролистывали работу, опубликованную ими за несколько месяцев до этого – и вдруг поняли, что наткнулись на нечто серьёзное.

Десятилетиями специалисты по информатике пытались разработать быстрый алгоритм для определения того, можно ли добавить к определённому графу рёбра так, чтобы он остался «планарным» – то есть, чтобы его рёбра не пересекались. Однако ни у кого не получалось улучшить алгоритм, опубликованный более 20 лет назад.

Хольм и Ротенберг с удивлением обнаружили, что в их работе есть идея, позволявшая достаточно сильно улучшить этот алгоритм. Она «разобралась с одним из главных препятствий на пути к реальному алгоритму», — сказал Хольм, специалист по информатике из Копенгагенского университета. «Возможно, мы полностью раскрыли этот вопрос».

Парочка поспешила приступить к работе над новой статьёй. Они представили её в июне на симпозиуме по вычислительной теории, проводимом Ассоциацией вычислительной техники, где подробно описали метод проверки графа на планарность, превосходящий предыдущий вариант экспоненциально.

Просмотров: 8 | Добавил: niko | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Поиск

Календарь
«  Октябрь 2020  »
ПнВтСрЧтПтСбВс
   1234
567891011
12131415161718
19202122232425
262728293031

Форма входа

nixp.ru

OpenNet

Новые программы

SLO.ru

Погода
Яндекс.Погода

Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz

  • Архив записей

    Copyright MyCorp © 2020