Asymptotically optimal dualization algorithms
E. V. DjukovaDorodnicyn Computing Center, Russian Academy of Sciences, ul. Vavilova 40, Moscow, 119333, RussiaP. A. ProkofjevRussian Academy of Sciences
2015en
ABI
Abstract
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.
Identifiers
Citations and references
Cited by 20 references