Прикладная дискретная математика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Прикладная дискретная математика, 2014, номер 1(23), страницы 96–105 (Mi pdm441)  
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

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

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

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

a Московский государственный университет им. М. В. Ломоносова, г. Москва, Россия
b Вычислительный центр им. А. А. Дородницына РАН, г. Москва, Россия
PDF полного текста (985 kB) Список цитирования (3)
Список литературы:
PDF
HTML
Аннотация: Рассматривается задача перечисления неприводимых покрытий булевой матрицы, известная как задача дуализации. Эффективность алгоритма дуализации принято оценивать сложностью шага алгоритма (построения очередного неприводимого покрытия). Рассматривается подход к построению алгоритма дуализации, эффективного в “типичном случае”. Подход основан на понятии асимптотически оптимального алгоритма с полиномиальной задержкой. Строятся две модификации предложенного ранее алгоритма АО2, позволяющие существенно сократить временные затраты в экспериментах со случайными булевыми матрицами.
Ключевые слова: булева матрица, перечисление неприводимых покрытий, асимптотически оптимальный алгоритм дуализации, нормальная форма монотонной булевой функции, минимальное вершинное покрытие гиперграфа.
Тип публикации: Статья
УДК: 519.1+519.8
Образец цитирования: Е. В. Дюкова, П. А. Прокофьев, “Об асимптотически оптимальном перечислении неприводимых покрытий булевой матрицы”, ПДМ, 2014, № 1(23), 96–105
Цитирование в формате AMSBIB
\RBibitem{DyuPro14}
\by Е.~В.~Дюкова, П.~А.~Прокофьев
\paper Об асимптотически оптимальном перечислении неприводимых покрытий булевой матрицы
\jour ПДМ
\yr 2014
\issue 1(23)
\pages 96--105
\mathnet{http://mi.mathnet.ru/pdm441}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/pdm441
  • https://www.mathnet.ru/rus/pdm/y2014/i1/p96
    • Эта публикация цитируется в следующих 3 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Прикладная дискретная математика
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024