Скобелев В. Г. Локальные алгоритмы на графах / В. Г. Скобелев; НАН Украины. Ин-т приклад. математики и механики. - Донецк : ИПММ НАНУ, 2003. - 218 c. - Библиогр.: с. 217 - рус.Исследована разрешимость задач теории графов в классах алгоритмов с линейной емкостной сложностью и алгоритмов с линейной сложностью рабочей памяти. Для различных представлений графов рассмотрена сложность операций над графами, а также сложность решения задач построения всех основных типов путей, циклов и остовных деревьев. Показано, что ряд модельных задач дискретной математики и ее приложений (идентификация состояний конечного автомата, построение супервизора для автоматной модели системы дискретных событий, построение выигрышной стратегии в игре 2-х лиц на графе) не разрешим в данных классах алгоритмов. Індекс рубрикатора НБУВ: В126.3
Рубрики:
Шифр НБУВ: ВА641058 Пошук видання у каталогах НБУВ Додаткова інформація про автора(ів) публікації: (cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці) Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
|