Исследована разрешимость задач теории графов в классах алгоритмов с линейной емкостной сложностью и алгоритмов с линейной сложностью рабочей памяти. Для различных представлений графов рассмотрена сложность операций над графами, а также сложность решения задач построения всех основных типов путей, циклов и остовных деревьев. Показано, что ряд модельных задач дискретной математики и ее приложений (идентификация состояний конечного автомата, построение супервизора для автоматной модели системы дискретных событий, построение выигрышной стратегии в игре 2-х лиц на графе) не разрешим в данных классах алгоритмов.

• Скобелєв Володимир Геннадійович (фізико-математичні науки)

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"