Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, 2018, Volume 58, Number 12, Pages 2153–2168
DOI: https://doi.org/10.31857/S004446690003559-5 (Mi zvmmf10811) 		 
This article is cited in 4 scientific papers (total in 4 papers)

Monotone dualization problem and its generalizations: asymptotic estimates of the number of solutions

E. V. Djukova, Yu. I. Zhuravlev

Dorodnicyn Computing Center, Federal Research Center “Computer Science and Control”, Russian Academy of Sciences, Moscow, Russia
Citations (4)
References:
PDF
HTML
DOI: https://doi.org/10.31857/S004446690003559-5
Abstract: Issues related to the construction of efficient algorithms for intractable discrete problems are studied. Enumeration problems are considered. Their intractability has two aspects — exponential growth of the number of their solutions with increasing problem size and the complexity of finding (enumerating) these solutions. The basic enumeration problem is the dualization of a monotone conjunctive normal form or the equivalent problem of finding irreducible coverings of Boolean matrices. For the latter problem and its generalization for the case of integer matrices, asymptotics for the typical number of solutions are obtained. These estimates are required, in particular, to prove the existence of asymptotically optimal algorithms for monotone dualization and its generalizations.
Key words: intractable discrete problem, dualization of monotone conjunctive normal form, irreducible covering of Boolean matrix, irredundant covering of integer matrix, asymptotically optimal algorithm.
Funding agency Grant number
Russian Foundation for Basic Research 16-01-00445_а
English version:
Computational Mathematics and Mathematical Physics, 2018, Volume 58, Issue 12, Pages 2064–2077
DOI: https://doi.org/10.1134/S0965542518120102
Bibliographic databases:
Document Type: Article
UDC: 519.7
Language: Russian
Citation: E. V. Djukova, Yu. I. Zhuravlev, “Monotone dualization problem and its generalizations: asymptotic estimates of the number of solutions”, Zh. Vychisl. Mat. Mat. Fiz., 58:12 (2018), 2153–2168; Comput. Math. Math. Phys., 58:12 (2018), 2064–2077
Citation in format AMSBIB
\Bibitem{DyuZhu18}
\by E.~V.~Djukova, Yu.~I.~Zhuravlev
\paper Monotone dualization problem and its generalizations: asymptotic estimates of the number of solutions
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2018
\vol 58
\issue 12
\pages 2153--2168
\mathnet{http://mi.mathnet.ru/zvmmf10811}
\crossref{https://doi.org/10.31857/S004446690003559-5}
\elib{https://elibrary.ru/item.asp?id=36759183}
\transl
\jour Comput. Math. Math. Phys.
\yr 2018
\vol 58
\issue 12
\pages 2064--2077
\crossref{https://doi.org/10.1134/S0965542518120102}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000458237300014}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85062098601}
Linking options:
  • https://www.mathnet.ru/eng/zvmmf10811
  • https://www.mathnet.ru/eng/zvmmf/v58/i12/p2153
    • This publication is cited in the following 4 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024