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

Об асимптотически оптимальном перечислении неприводимых покрытий булевой матрицы | Прикладная дискретная математика. 2014. № 1(23).

Рассматривается задача перечисления неприводимых покрытий булевой матрицы, известная как задача дуализации. Эффективность алгоритма дуализации принято оценивать сложностью шага алгоритма (построения очередного неприводимого покрытия). Рассматривается подход к построению алгоритма дуализации, эффективного в «типичном случае». Подход основан на понятии асимптотически оптимального алгоритма с полиномиальной задержкой. Строятся две модификации предложенного ранее алгоритма АО2, позволяющие существенно сократить временные затраты в экспериментах со случайными булевыми матрицами.
  • Title Об асимптотически оптимальном перечислении неприводимых покрытий булевой матрицы
  • Headline Об асимптотически оптимальном перечислении неприводимых покрытий булевой матрицы
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 1(23)
  • Date:
  • DOI
Ключевые слова
булева матрица, перечисление неприводимых покрытий, асимптотически оптимальный алгоритм дуализации, нормальная форма монотонной булевой функции, минимальное вершинное покрытие гиперграфа, Boolean matrix, enumeration of irreducible coverings, asymptotically optimal algorithm for the dualization, CNF and DNF of monotonic Boolean function, minimal transversal of hypergraph
Авторы
Ссылки
Дюкова Е. В., Сотнезов Р. М. О сложности задачи дуализации // Журн. вычисл. матем. и матем. физ. 2012. Т. 52. №10. С. 1926-1935.
Дюкова Е. В., Инякин А. С. Асимптотически оптимальное построение тупиковых покрытий целочисленной матрицы // Математические вопросы кибернетики. 2008. Т. 17. С. 235-246.
Дюкова Е. В. О сложности реализации дискретных (логических) процедур распознавания // Журн. вычисл. матем. и матем. физики. 2004. Т. 44. №3. С. 562-572.
Дюкова Е. В. Об асимптотически оптимальном алгоритме построения тупиковых тестов // ДАН СССР. 1977. Т. 233. №4. С. 527-530.
Khachiyan L., Boros E., Elbassioni K., and Gurvich V. An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation // Discr. Appl. Math. 2006. V. 154. No. 16. P. 2350-2372. URL: http: //linkinghub.elsevier.com/retrieve/pii/S0166218X06001910.
Fredman M. L. and Khachiyan L. On the complexity of dualization of monotone disjunctive normal forms // J. Algorithms. 1996. V.21. P. 618-628.
Boros E., Gurvich V., Elbassioni K., and Khachiyan L. An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension // Parallel Process. Lett. 2000. V. 10. No. 4. P. 253-266. URL: http://www.worldscientific.com/doi/ abs/10.1142/S0129626400000251.
Boros E. and Elbassioni K. Generating maximal independent sets for hypergraphs with bounded edge-intersections // LATIN 2004: Theoretical Informatics. Berlin; Heidelberg: Springer, 2004. P. 488-498. URL: http://www.springerlink.com/index/ b9t9wx6ue9t9hvw3.pdf.
Eiter T., Gottlob G., and Makino K. New results on monotone dualization and generating hypergraph transversals // SIAM J. Comput. 2003. V.32. No. 2. P. 514-537.
Johnson D., Yannakakis M., and Papadimitriou C. On generating all maximal independent sets // Inform. Process. Lett. 1988. V.27. No.3. P. 119-123. URL: http://www. sciencedirect.com/science/article/pii/0020019088900658.
Об асимптотически оптимальном перечислении неприводимых покрытий булевой матрицы | Прикладная дискретная математика. 2014. № 1(23).
Об асимптотически оптимальном перечислении неприводимых покрытий булевой матрицы | Прикладная дискретная математика. 2014. № 1(23).
Полнотекстовая версия