On Construction of the Set of Irreducible Partial Covers

  • Mikhail Ju. Moshkov
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)


In the paper a totally polynomial algorithm for construction of the set of irreducible partial covers for the major part of set cover problems is considered.


Irreducible partial cover totally polynomial algorithm 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Boros, E., Hammer, P.L., Ibaraki, T., Kawakami, K.: Polynomial time recognition of 2-monotonic positive Boolean functions given by an oracle. SIAM J. Computing 26(1), 93–109 (1997)zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Chegis, I.A., Yablonskii, S.V.: Logical methods of electric circuit control. Trudy MIAN SSSR 51, 270–360 (1958) (in Russian) Google Scholar
  3. 3.
    Korshunov, A.D.: On the number of monotone Boolean functions. Problemy Kibernetiki 38, 5–108 (1981) (in Russian)Google Scholar
  4. 4.
    Makino, K., Ibaraki, T.: The maximum latency and identification of positive Boolean functions. SIAM J. Computing 26(5), 1363–1383 (1997)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    Pawlak, Z.: Rough Sets – Theoretical Aspects of Reasoning about Data. Kluwer Academic Publishers, Dordrecht (1991)zbMATHGoogle Scholar
  6. 6.
    Shmulevich, I., Korshunov, A.D., Astola, J.: Almost all monotone Boolean functions are polynomially lernable using membership queries. Information Processing Letters 79, 211–213 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Skowron, A.: Rough sets in KDD. In: Proceedings of the 16-th World Computer Congress (IFIP 2000). Beijing, China, pp. 1–14 (2000)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Mikhail Ju. Moshkov
    • 1
    • 2
  1. 1.Foundation for Support of Agrarian Reform and Rural DevelopmentMoscowRussia
  2. 2.Institute of Computer ScienceUniversity of SilesiaSosnowiecPoland

Personalised recommendations