Discrete extremal problems on covering

1. Kruskal, J.B., On the shortest spanning subtree of a graph and the travelling salesman problem. Proc Amer. Math. Soc., 7(1956), 48–50.

   Google Scholar 

2. Garey, M.R., D.S. Johnson, Computers and intractability. A guine to the theory of NP-completeness. N.H.Freeman and Company, San Francisco, 1979.

   Google Scholar 

3. Сапоженко, А.А., А.С. Асратян, Н.Н. Кузюрин, Обзор некоторых результатов по задачам о покрытии. Дискретный анадиз, 30(1977), 46–75.

   Google Scholar 

4. Holyer, I., The NP-completeness of edge-coloring. SIAM J. on Computing, 10(1981), 718–720.

   Google Scholar 

5. Визинг, В.Г, Об оценке хроматицеского класса р-графа. Дискретный анализ, 3(1964), 25–30.

   Google Scholar 

6. Сердюков, А.И., О некоторых экстремалъных обходах в графах. Управляемые системы, 17(1978), 76–79.

   Google Scholar 

7. Christofides, N., Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report, Graduate School of Industrial Administration, Carnegue-Mellon University, Pittsburgh, PA, 1976.

   Google Scholar 

8. Cornuejols, G., G.L. Nemhauser, Tight bounds for Christofides' travelling salesman heuristic. Math. Programming, 14(1978), 116–121.

   Google Scholar 

9. Johnson, S.M., Optimal two-and three-stage production schedules with setup times included. Naval Res. Logist. Quart., 1(1954), 61–68.

   Google Scholar 

10. Johnson, D.S., Near-optimal bin packing algorithms. Doctoral Thesis, Dept. of Mathematics, MIT, Cambridge, MA, 1973.

    Google Scholar 

11. Sahni, S., T. Gonzales, P-complete problems and approximate solutions. Proc. 15th annual symposium on swithing and automata theory, IEEE, Long Beach, 1974, 28–32.

    Google Scholar 

12. Garey, M.R., D.S. Johnson, The complexity of near-optimal graph coloring, J. Assoc. Comput. Mach., 23(1976), 43–49.

    Google Scholar 

13. Нигматуллин, Р.Г. Сложность приближенного решения комбинаторных задач. Докл. АН СССР, 224(1975), 289–292.

    Google Scholar 

14. Нигматуллин, Р.Г., О приближенных алгоритмах с ограниченной абсолютной погрещностью для дискретных экстремальных задач. Кибернетика, I(1978), 95–101.

    Google Scholar 

15. Gimpel, J.F., A method of producing of a Boolean function having an arbitrary prescribed prime implicant table. IEEE Trans. on Electron. Computers, 14(1965), 485–488.

    Google Scholar 

16. Нечипорук, Э.И., О сложности вентельных схем, реалезующих булевские матрицы с неопределенными элементами. Докл. АН СССР, 163 (1965), 40–43.

    Google Scholar 

17. Нигматуллин, Р.Г., Метод наискорейшего спуска в задачах на покрытие. Вопросы точности и эффективности алгоритмов Труды симпозиума, Киев, 5 (1969), 116–126.

    Google Scholar 

18. Karp, R.M., Reducibility among combinatorial problems. Complexity of Computer Computations, Plenum Press, New York, 1972, 85–103.

    Google Scholar 

19. Коршунов, А.Д., О числе внутренней устойчивости графов. Кибернетика Киев, 1(1974), 17–26.

    Google Scholar 

20. Коршунов, А.Л., О хроматическом числе n-вершинных графов. Методы дискретного анализа, 35(1980), 15–44.

    Google Scholar 

21. Grimmett, G.R., C.J.H. McDiarmid, On coloring random graphs. Math. Proc. Cambridge Phil. Soc., 77(1975), 313–324.

    Google Scholar 

22. Кузнецов, С.Е., О нижней оценке длины кратчайшей д.н.ф. почти всех булевых функций. Вероятностные методы и кибернетика, Казань, 19(1983), 44–47.

    Google Scholar 

23. Глаголев, В.В., Оценка сложности сокращенной дизьюнктивной нормальной формы для почти всех функций алгебры логики. Докл. АН СССР, 158(1964), № 4, 770–773.

    Google Scholar 

24. Нигматуллин, Р.Г., Вариационный принцип в алгебре логики. Дискретный анализ, 10(1967), 69–89.

    Google Scholar 

25. Корщунов, А.Д., О сложности кратчайших дизьюнктивных нормальных форм булевых функций. Методы дискретного анализа, 37(1981), 9–41.

    Google Scholar 

26. Коршунов, А.Д., О сложности кратчайших дизьюнктивных нормальных форм случайных булевых функций. Методы дискретного анализа, 40(1983), 25–53.

    Google Scholar 

Translation of Russian references

1. Sapoženko, A.A., A.C. Asratjan, N.N. Kuzjurin, A survey of some results on covering problems. Metody Diskret. Analiz., 30(1977), 46–75.

   Google Scholar 

2. Vizing, V.G., On a estimate of the chromatic class of a p-graph. Diskret. Analiz, 3(1964), 25–30.

   Google Scholar 

3. Serdjukov, A.T., Some extremal bypasses in graphs. Upravljaemye Systemy, 17(1978), 76–79.

   Google Scholar 

4. Nigmatullin, R.G., The complexity of the approximate solution of combinatorial problems. Dokl. Akad. Nauk SSSR, 224(1975), 289–292.

   Google Scholar 

5. Nigmatullin, R.G., On approximate algorithms with restricted absolute error for discrete extremal problems. Kibernetika (Kiev), 1(1978),95–101.

   Google Scholar 

6. Nečiporuk, E.T., On the complexity of gata networks realizing Boolean matrices with indefinite elements. Kokl. Akad. Nauk SSSR, 163(1965), 40–43.

   Google Scholar 

7. Nigmatullin, R.G., A method of steepest descent in problems on covering. Questions of precision and effectiveness of algorithms, Kiev, 5(1969), 116–126.

   Google Scholar 

8. Korshunov, A.D., The number of inner stability of graphs. Kibernetika (Kiev), 1(1974), 17–28.

   Google Scholar 

9. Korshunov, A.D., The chromatic number of n-vertex graphs. Metody Diskret. Analiz., 35(1980), 15–44.

   Google Scholar 

10. Kuznetsov, S.E., On the lower estimate for the length of the shortest disjunctive normal form for almost all Boolean functions. Probabilistic Methods and Cybernetics, 19(1983), 44–47.

    Google Scholar 

11. Glagolev, V.V., An estimate of the complexity of the contracted disjunctive normal form for almost all functions of the logic of algebra. Dokl. Akad. Nauk SSSR, 158(1964), 770–773.

    Google Scholar 

12. Nigmatullin, R.G., The variational principle in the algebra of logic. Diskret. Analiz, 10(1967), 69–89.

    Google Scholar 

13. Korshunov, A.D., On the complexity of the shortest disjunctive normal of Boolean functions. Metody Diskret. Analiz., 37(1981), 9–41.

    Google Scholar 

14. Korshunov, A.D., On the complexity of the shortest disjunctive normal forms of random Boolean functions. Metody Diskret. Analiz., 40(1983), 25–53.

    Google Scholar 

Download references