Geodesic
Asymptotically optimal dualization algorithms
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 5, pp. 895-910 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The design of efficient on average algorithms for discrete enumeration problems is studied. The dualization problem, which is a central enumeration problem, is considered. New asymptotically optimal dualization algorithms are constructed. It is shown that they are superior in time costs to earlier constructed asymptotically optimal dualization algorithms and other available dualization algorithms with different design features. 
@article{ZVMMF_2015_55_5_a14,
     author = {E. V. Djukova and P. A. Prokofjev},
     title = {Asymptotically optimal dualization algorithms},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {895--910},
     year = {2015},
     volume = {55},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_5_a14/}
}
TY  - JOUR
AU  - E. V. Djukova
AU  - P. A. Prokofjev
TI  - Asymptotically optimal dualization algorithms
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2015
SP  - 895
EP  - 910
VL  - 55
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_5_a14/
LA  - ru
ID  - ZVMMF_2015_55_5_a14
ER  - 
%0 Journal Article
%A E. V. Djukova
%A P. A. Prokofjev
%T Asymptotically optimal dualization algorithms
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2015
%P 895-910
%V 55
%N 5
%U http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_5_a14/
%G ru
%F ZVMMF_2015_55_5_a14
E. V. Djukova; P. A. Prokofjev. Asymptotically optimal dualization algorithms. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 5, pp. 895-910. http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_5_a14/

[1] Johnson D., Yannakakis M., Papadimitriou S., “On generating all maximal independent sets”, Information Proc. Letters, 27:3 (1988), 119–123 | MR | Zbl

[2] Eiter T., Gottlob G., Makino K., “New results on monotone dualization and generating hypergraph transversals”, SIAM J. Comput., 32:2 (2003), 514–537 | MR | Zbl

[3] Fredman M. L., Khachiyan L., “On the complexity of dualization of monotone disjunctive normal forms”, J. Algorithms, 21 (1996), 618–628 | MR | Zbl

[4] Khachiyan L., Bows E., Elbassioni K., Gurvich V., “An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation”, Discrete Applied Mathematics, 154:16 (2006), 2350–2372 | MR | Zbl

[5] Boros E., Elbassioni K., “Generating maximal independent sets for hypergraphs with bounded edge-intersections”, LATIN 2004: Theoretical Informatics, Springer, Berlin–Heidelberg, 2004, 488–498 | MR | Zbl

[6] Boros E., Gurvich V., Elbassioni K., Khachiyan L., “An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension”, Parallel Processing Letters, 10:4 (2000), 253–266 | MR

[7] Dyukova E. V., “Ob asimptoticheski optimalnom algoritme postroeniya tupikovykh testov”, Dokl. AN SSSR, 233:4 (1977), 527–530 | MR | Zbl

[8] Djukova E. V., “Discrete recognition procedures: the complexity of realization”, Pattern Recognition and Image Analysis, 13:1 (2003), 8–10

[9] Djukova E. V., Sotnezov R. M., “On the complexity of discrete generation problems”, Doklady Mathematics, 82:3 (2010), 847–849 | MR

[10] Djukova E. V., Zhuravlev Yu. I., “Discrete methods of information analysis in recognition and algorithm synthesis”, Pattern Recognition and Image Analisys, 7:2 (1997), 192–207

[11] Dyukova E. V., “O slozhnosti realizatsii nekotorykh protsedur raspoznavaniya”, Zh. vychisl. matem. i matem. fiz., 27:1 (1987), 114–127 | MR | Zbl

[12] Dyukova E. V., “O slozhnosti realizatsii diskretnykh (logicheskikh) protsedur raspoznavaniya”, Zh. vychisl. matem. i matem. fiz., 44:3 (2004), 562–572 | MR | Zbl

[13] Dyukova E. V., Zhuravlev Yu. I., “Diskretnyi analiz priznakovykh opisanii v zadachakh raspoznavaniya bolshoi razmernosti”, Zh. vychisl. matem. i matem. fiz., 40:8 (2000), 1264–1278 | MR | Zbl

[14] Dyukova E. V., Inyakin A. S., “Asimptoticheski optimalnoe postroenie tupikovykh pokrytii tselochislennoi matritsy”, Matematicheskie voprosy kibernetiki, 17 (2008), 235–246

[15] Dyukova E. V., Sotnezov P. M., “O slozhnosti zadachi dualizatsii”, Zh. vychisl. matem. i matem. fiz., 52:10 (2012), 1926–1935 | Zbl

[16] Dyukova E. V., Prokofev P. A., “Ob asimptoticheski optimalnom perechislenii neprivodimykh pokrytii bulevoi matritsy”, Prikladnaya diskretnaya matematika, 2014, no. 1, 96–105

[17] Murakami K., Uno T., “Efficient algorithms for dualizing large-scale hypergraphs”, Proc. 15th Meeting on Algorithm Engineering and Experiments, ALENEX 2013 (New Orleans, Louisiana, USA, 2013), SIAM, 2013 | MR

[18] Murakami K., Uno T., “Efficient algorithms for dualizing large-scale hypergraphs”, Discrete Applied Mathematics, 170 (2014), 83–94 | MR | Zbl

[19] UCI machine learning repository, http://archive.ics.uci.edu/ml/

[20] Frequent itemset mining dataset repository, http://fimi.ua.ac.be/data/