Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Препринт ИПМ № 84, Москва, 2003 г.
Авторы: Кочкаров А. А., Кочкаров Р.А.
Параллельные алгоритмы на предфрактальных графах
Аннотация:
Работа посвящена параллельным алгоритмам решения некоторых задач на предфрактальных графах: поиск (1) остовного дерева минимального веса, (2) совершенного паросочетания, (3) эйлеровой цепи, (4) гамильтонова цикла. Алгоритм (1) исполняется за время O(n2), используя O(nL) процессоров, а алгоритм (2) за время O(n3) при использовании O(nL-1) процессоров, где размерность обоих задач O(nL). Алгоритмы (3) и (4) также исполняются за полиномиальное время.   Алгоритм (3) исполняется за    время O(q), используя O(nL) процессоров.
Язык публикации: русский,  страниц: 18
Направление исследований:
Математическое моделирование в актуальных проблемах науки и техники
Полный текст на русском языке:
Статистика просмотров (обновляется раз в сутки):
за последние 30 дней — 11 (-1), всего с 01.09.2019 — 278
Сведения об авторах:
  • Кочкаров Азрет Ахматович,  ИПМ им. М.В. Келдыша РАН
  • Кочкаров Р.А.