{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:11:12Z","timestamp":1725459072411},"publisher-location":"Berlin\/Heidelberg","reference-count":26,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540156895"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028803","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T17:15:07Z","timestamp":1138209307000},"page":"191-207","source":"Crossref","is-referenced-by-count":0,"title":["Discrete extremal problems on covering"],"prefix":"10.1007","author":[{"given":"A. D.","family":"Korshunov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J.B. Kruskal","year":"1956","unstructured":"Kruskal, J.B., On the shortest spanning subtree of a graph and the travelling salesman problem. Proc Amer. Math. Soc., 7(1956), 48\u201350.","journal-title":"Proc Amer. Math. Soc."},{"key":"19_CR2","volume-title":"Computers and intractability. A guine to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"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."},{"key":"19_CR3","first-page":"46","volume":"30","author":"\u0410.\u0410. \u0421\u0430\u043f\u043e\u0436\u0435\u043d\u043a\u043e","year":"1977","unstructured":"\u0421\u0430\u043f\u043e\u0436\u0435\u043d\u043a\u043e, \u0410.\u0410., \u0410.\u0421. \u0410\u0441\u0440\u0430\u0442\u044f\u043d, \u041d.\u041d. \u041a\u0443\u0437\u044e\u0440\u0438\u043d, \u041e\u0431\u0437\u043e\u0440 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432 \u043f\u043e \u0437\u0430\u0434\u0430\u0447\u0430\u043c \u043e \u043f\u043e\u043a\u0440\u044b\u0442\u0438\u0438. \u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u0430\u043d\u0430\u0434\u0438\u0437, 30(1977), 46\u201375.","journal-title":"\u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u0430\u043d\u0430\u0434\u0438\u0437"},{"key":"19_CR4","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Holyer, I., The NP-completeness of edge-coloring. SIAM J. on Computing, 10(1981), 718\u2013720.","journal-title":"SIAM J. on Computing"},{"key":"19_CR5","first-page":"25","volume":"3","author":"\u0412.\u0413 \u0412\u0438\u0437\u0438\u043d\u0433","year":"1964","unstructured":"\u0412\u0438\u0437\u0438\u043d\u0433, \u0412.\u0413, \u041e\u0431 \u043e\u0446\u0435\u043d\u043a\u0435 \u0445\u0440\u043e\u043c\u0430\u0442\u0438\u0446\u0435\u0441\u043a\u043e\u0433\u043e \u043a\u043b\u0430\u0441\u0441\u0430 \u0440-\u0433\u0440\u0430\u0444\u0430. \u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u0430\u043d\u0430\u043b\u0438\u0437, 3(1964), 25\u201330.","journal-title":"\u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u0430\u043d\u0430\u043b\u0438\u0437"},{"key":"19_CR6","first-page":"76","volume":"17","author":"\u0410.\u0418. \u0421\u0435\u0440\u0434\u044e\u043a\u043e\u0432","year":"1978","unstructured":"\u0421\u0435\u0440\u0434\u044e\u043a\u043e\u0432, \u0410.\u0418., \u041e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u044d\u043a\u0441\u0442\u0440\u0435\u043c\u0430\u043b\u044a\u043d\u044b\u0445 \u043e\u0431\u0445\u043e\u0434\u0430\u0445 \u0432 \u0433\u0440\u0430\u0444\u0430\u0445. \u0423\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u043c\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b, 17(1978), 76\u201379.","journal-title":"\u0423\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u043c\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b"},{"key":"19_CR7","volume-title":"Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report, Graduate School of Industrial Administration","author":"N. Christofides","year":"1976","unstructured":"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."},{"key":"19_CR8","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF01588956","volume":"14","author":"G. Cornuejols","year":"1978","unstructured":"Cornuejols, G., G.L. Nemhauser, Tight bounds for Christofides' travelling salesman heuristic. Math. Programming, 14(1978), 116\u2013121.","journal-title":"Math. Programming"},{"key":"19_CR9","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"S.M. Johnson","year":"1954","unstructured":"Johnson, S.M., Optimal two-and three-stage production schedules with setup times included. Naval Res. Logist. Quart., 1(1954), 61\u201368.","journal-title":"Naval Res. Logist. Quart."},{"key":"19_CR10","volume-title":"Near-optimal bin packing algorithms","author":"D.S. Johnson","year":"1973","unstructured":"Johnson, D.S., Near-optimal bin packing algorithms. Doctoral Thesis, Dept. of Mathematics, MIT, Cambridge, MA, 1973."},{"key":"19_CR11","first-page":"28","volume-title":"P-complete problems and approximate solutions","author":"S. Sahni","year":"1974","unstructured":"Sahni, S., T. Gonzales, P-complete problems and approximate solutions. Proc. 15th annual symposium on swithing and automata theory, IEEE, Long Beach, 1974, 28\u201332."},{"key":"19_CR12","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/321921.321926","volume":"23","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., D.S. Johnson, The complexity of near-optimal graph coloring, J. Assoc. Comput. Mach., 23(1976), 43\u201349.","journal-title":"J. Assoc. Comput. Mach."},{"key":"19_CR13","first-page":"289","volume":"224","author":"\u0420.\u0413. \u041d\u0438\u0433\u043c\u0430\u0442\u0443\u043b\u043b\u0438\u043d","year":"1975","unstructured":"\u041d\u0438\u0433\u043c\u0430\u0442\u0443\u043b\u043b\u0438\u043d, \u0420.\u0413. \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0442\u043e\u0440\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447. \u0414\u043e\u043a\u043b. \u0410\u041d \u0421\u0421\u0421\u0420, 224(1975), 289\u2013292.","journal-title":"\u0414\u043e\u043a\u043b. \u0410\u041d \u0421\u0421\u0421\u0420"},{"key":"19_CR14","first-page":"95","volume":"I","author":"\u0420.\u0413. \u041d\u0438\u0433\u043c\u0430\u0442\u0443\u043b\u043b\u0438\u043d","year":"1978","unstructured":"\u041d\u0438\u0433\u043c\u0430\u0442\u0443\u043b\u043b\u0438\u043d, \u0420.\u0413., \u041e \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u0445 \u0441 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u043e\u0439 \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u043e\u0439 \u043f\u043e\u0433\u0440\u0435\u0449\u043d\u043e\u0441\u0442\u044c\u044e \u0434\u043b\u044f \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0445 \u044d\u043a\u0441\u0442\u0440\u0435\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447. \u041a\u0438\u0431\u0435\u0440\u043d\u0435\u0442\u0438\u043a\u0430, I(1978), 95\u2013101.","journal-title":"\u041a\u0438\u0431\u0435\u0440\u043d\u0435\u0442\u0438\u043a\u0430"},{"key":"19_CR15","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1109\/PGEC.1965.264175","volume":"14","author":"J.F. Gimpel","year":"1965","unstructured":"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\u2013488.","journal-title":"IEEE Trans. on Electron. Computers"},{"key":"19_CR16","first-page":"40","volume":"163","author":"\u042d.\u0418. \u041d\u0435\u0447\u0438\u043f\u043e\u0440\u0443\u043a","year":"1965","unstructured":"\u041d\u0435\u0447\u0438\u043f\u043e\u0440\u0443\u043a, \u042d.\u0418., \u041e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0432\u0435\u043d\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0441\u0445\u0435\u043c, \u0440\u0435\u0430\u043b\u0435\u0437\u0443\u044e\u0449\u0438\u0445 \u0431\u0443\u043b\u0435\u0432\u0441\u043a\u0438\u0435 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0441 \u043d\u0435\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u043c\u0438. \u0414\u043e\u043a\u043b. \u0410\u041d \u0421\u0421\u0421\u0420, 163 (1965), 40\u201343.","journal-title":"\u0414\u043e\u043a\u043b. \u0410\u041d \u0421\u0421\u0421\u0420"},{"key":"19_CR17","first-page":"116","volume":"5","author":"\u0420.\u0413. \u041d\u0438\u0433\u043c\u0430\u0442\u0443\u043b\u043b\u0438\u043d","year":"1969","unstructured":"\u041d\u0438\u0433\u043c\u0430\u0442\u0443\u043b\u043b\u0438\u043d, \u0420.\u0413., \u041c\u0435\u0442\u043e\u0434 \u043d\u0430\u0438\u0441\u043a\u043e\u0440\u0435\u0439\u0448\u0435\u0433\u043e \u0441\u043f\u0443\u0441\u043a\u0430 \u0432 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u043d\u0430 \u043f\u043e\u043a\u0440\u044b\u0442\u0438\u0435. \u0412\u043e\u043f\u0440\u043e\u0441\u044b \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0438 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0422\u0440\u0443\u0434\u044b \u0441\u0438\u043c\u043f\u043e\u0437\u0438\u0443\u043c\u0430, \u041a\u0438\u0435\u0432, 5 (1969), 116\u2013126.","journal-title":"\u0412\u043e\u043f\u0440\u043e\u0441\u044b \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0438 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0422\u0440\u0443\u0434\u044b \u0441\u0438\u043c\u043f\u043e\u0437\u0438\u0443\u043c\u0430"},{"key":"19_CR18","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Reducibility among combinatorial problems. Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M., Reducibility among combinatorial problems. Complexity of Computer Computations, Plenum Press, New York, 1972, 85\u2013103."},{"key":"19_CR19","first-page":"17","volume":"1","author":"\u0410.\u0414. \u041a\u043e\u0440\u0448\u0443\u043d\u043e\u0432","year":"1974","unstructured":"\u041a\u043e\u0440\u0448\u0443\u043d\u043e\u0432, \u0410.\u0414., \u041e \u0447\u0438\u0441\u043b\u0435 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0439 \u0443\u0441\u0442\u043e\u0439\u0447\u0438\u0432\u043e\u0441\u0442\u0438 \u0433\u0440\u0430\u0444\u043e\u0432. \u041a\u0438\u0431\u0435\u0440\u043d\u0435\u0442\u0438\u043a\u0430 \u041a\u0438\u0435\u0432, 1(1974), 17\u201326.","journal-title":"\u041a\u0438\u0431\u0435\u0440\u043d\u0435\u0442\u0438\u043a\u0430"},{"key":"19_CR20","first-page":"15","volume":"35","author":"\u0410.\u041b. \u041a\u043e\u0440\u0448\u0443\u043d\u043e\u0432","year":"1980","unstructured":"\u041a\u043e\u0440\u0448\u0443\u043d\u043e\u0432, \u0410.\u041b., \u041e \u0445\u0440\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0447\u0438\u0441\u043b\u0435 n-\u0432\u0435\u0440\u0448\u0438\u043d\u043d\u044b\u0445 \u0433\u0440\u0430\u0444\u043e\u0432. \u041c\u0435\u0442\u043e\u0434\u044b \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0430\u043d\u0430\u043b\u0438\u0437\u0430, 35(1980), 15\u201344.","journal-title":"\u041c\u0435\u0442\u043e\u0434\u044b \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0430\u043d\u0430\u043b\u0438\u0437\u0430"},{"key":"19_CR21","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1017\/S0305004100051124","volume":"77","author":"G.R. Grimmett","year":"1975","unstructured":"Grimmett, G.R., C.J.H. McDiarmid, On coloring random graphs. Math. Proc. Cambridge Phil. Soc., 77(1975), 313\u2013324.","journal-title":"Math. Proc. Cambridge Phil. Soc."},{"key":"19_CR22","first-page":"44","volume":"19","author":"\u0421.\u0415. \u041a\u0443\u0437\u043d\u0435\u0446\u043e\u0432","year":"1983","unstructured":"\u041a\u0443\u0437\u043d\u0435\u0446\u043e\u0432, \u0421.\u0415., \u041e \u043d\u0438\u0436\u043d\u0435\u0439 \u043e\u0446\u0435\u043d\u043a\u0435 \u0434\u043b\u0438\u043d\u044b \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0439 \u0434.\u043d.\u0444. \u043f\u043e\u0447\u0442\u0438 \u0432\u0441\u0435\u0445 \u0431\u0443\u043b\u0435\u0432\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439. \u0412\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u0438 \u043a\u0438\u0431\u0435\u0440\u043d\u0435\u0442\u0438\u043a\u0430, \u041a\u0430\u0437\u0430\u043d\u044c, 19(1983), 44\u201347.","journal-title":"\u0412\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u0438 \u043a\u0438\u0431\u0435\u0440\u043d\u0435\u0442\u0438\u043a\u0430"},{"issue":"4","key":"19_CR23","first-page":"770","volume":"158","author":"\u0412.\u0412. \u0413\u043b\u0430\u0433\u043e\u043b\u0435\u0432","year":"1964","unstructured":"\u0413\u043b\u0430\u0433\u043e\u043b\u0435\u0432, \u0412.\u0412., \u041e\u0446\u0435\u043d\u043a\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u043d\u043e\u0439 \u0434\u0438\u0437\u044c\u044e\u043d\u043a\u0442\u0438\u0432\u043d\u043e\u0439 \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0444\u043e\u0440\u043c\u044b \u0434\u043b\u044f \u043f\u043e\u0447\u0442\u0438 \u0432\u0441\u0435\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439 \u0430\u043b\u0433\u0435\u0431\u0440\u044b \u043b\u043e\u0433\u0438\u043a\u0438. \u0414\u043e\u043a\u043b. \u0410\u041d \u0421\u0421\u0421\u0420, 158(1964), \u2116 4, 770\u2013773.","journal-title":"\u0414\u043e\u043a\u043b. \u0410\u041d \u0421\u0421\u0421\u0420"},{"key":"19_CR24","first-page":"69","volume":"10","author":"\u0420.\u0413. \u041d\u0438\u0433\u043c\u0430\u0442\u0443\u043b\u043b\u0438\u043d","year":"1967","unstructured":"\u041d\u0438\u0433\u043c\u0430\u0442\u0443\u043b\u043b\u0438\u043d, \u0420.\u0413., \u0412\u0430\u0440\u0438\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0439 \u043f\u0440\u0438\u043d\u0446\u0438\u043f \u0432 \u0430\u043b\u0433\u0435\u0431\u0440\u0435 \u043b\u043e\u0433\u0438\u043a\u0438. \u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u0430\u043d\u0430\u043b\u0438\u0437, 10(1967), 69\u201389.","journal-title":"\u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u0430\u043d\u0430\u043b\u0438\u0437"},{"key":"19_CR25","first-page":"9","volume":"37","author":"\u0410.\u0414. \u041a\u043e\u0440\u0449\u0443\u043d\u043e\u0432","year":"1981","unstructured":"\u041a\u043e\u0440\u0449\u0443\u043d\u043e\u0432, \u0410.\u0414., \u041e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0445 \u0434\u0438\u0437\u044c\u044e\u043d\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u0444\u043e\u0440\u043c \u0431\u0443\u043b\u0435\u0432\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439. \u041c\u0435\u0442\u043e\u0434\u044b \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0430\u043d\u0430\u043b\u0438\u0437\u0430, 37(1981), 9\u201341.","journal-title":"\u041c\u0435\u0442\u043e\u0434\u044b \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0430\u043d\u0430\u043b\u0438\u0437\u0430"},{"key":"19_CR26","first-page":"25","volume":"40","author":"\u0410.\u0414. \u041a\u043e\u0440\u0448\u0443\u043d\u043e\u0432","year":"1983","unstructured":"\u041a\u043e\u0440\u0448\u0443\u043d\u043e\u0432, \u0410.\u0414., \u041e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0445 \u0434\u0438\u0437\u044c\u044e\u043d\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u0444\u043e\u0440\u043c \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0431\u0443\u043b\u0435\u0432\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439. \u041c\u0435\u0442\u043e\u0434\u044b \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0430\u043d\u0430\u043b\u0438\u0437\u0430, 40(1983), 25\u201353.","journal-title":"\u041c\u0435\u0442\u043e\u0434\u044b \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0430\u043d\u0430\u043b\u0438\u0437\u0430"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028803.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:59:00Z","timestamp":1607551140000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028803"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540156895"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/bfb0028803","relation":{},"subject":[]}}