Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  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
Направление исследований:
Математическое моделирование в актуальных проблемах науки и техники
Полный текст: Сведения об авторах:
  • Кочкаров Азрет Ахматович,  ИПМ им. М.В. Келдыша РАН
  • Кочкаров Р.А.