Е. В. Дюкова, П. А. Прокофьев, “Об асимптотически оптимальном перечислении неприводимых покрытий булевой матрицы”, ПДМ, 2014, номер 1(23),страницы 96

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

Вычислительные методы в дискретной математике

Об асимптотически оптимальном перечислении неприводимых покрытий булевой матрицы

Е. В. Дюкова^ab, П. А. Прокофьев^b

^a Московский государственный университет им. М. В. Ломоносова, г. Москва, Россия
^b Вычислительный центр им. А. А. Дородницына РАН, г. Москва, Россия

Аннотация: Рассматривается задача перечисления неприводимых покрытий булевой матрицы, известная как задача дуализации. Эффективность алгоритма дуализации принято оценивать сложностью шага алгоритма (построения очередного неприводимого покрытия). Рассматривается подход к построению алгоритма дуализации, эффективного в “типичном случае”. Подход основан на понятии асимптотически оптимального алгоритма с полиномиальной задержкой. Строятся две модификации предложенного ранее алгоритма АО2, позволяющие существенно сократить временные затраты в экспериментах со случайными булевыми матрицами.

Ключевые слова: булева матрица, перечисление неприводимых покрытий, асимптотически оптимальный алгоритм дуализации, нормальная форма монотонной булевой функции, минимальное вершинное покрытие гиперграфа.

УДК: 519.1+519.8