Ли Вен Ся, Е. М. Патрикеев, Сяо Дон Мей, “ДНК-алгоритм для задачи о наибольшем паросочетании”, Автомат. и телемех., 2015, выпуск 10,страницы 106

Эта публикация цитируется в 7 статьях

Системный анализ и исследование операций

ДНК-алгоритм для задачи о наибольшем паросочетании

Ли Вен Ся^a, Е. М. Патрикеев^a, Сяо Дон Мей^b

^a Восточно-китайский педагогический университет, Шанхай, КНР
^b Шанхайский транспортный университет, Шанхай, КНР

Аннотация: Предлагается процедура решения классической дискретной экстремальной задачи о наибольшем паросочетании с применением модели Адлемана–Липтона в качестве вычислительной архитектуры. Показано, что для неориентированного графа с $n$ ребрами решение получается за $O(n^2)$ шагов.

Статья представлена к публикации членом редколлегии: В. И. Гурман

Поступила в редакцию: 20.01.2015