{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:43:53Z","timestamp":1725489833956},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540427070"},{"type":"electronic","value":"9783540454779"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45477-2_7","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T07:09:01Z","timestamp":1187248141000},"page":"55-65","source":"Crossref","is-referenced-by-count":2,"title":["On Constrained Minimum Vertex Covers of Bipartite Graphs: Improved Algorithms"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Iyad A.","family":"Kanj","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,10,2]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(97)00213-5","volume":"65","author":"R. Balasubramanian","year":"1998","unstructured":"R. Balasubramanian, M, R. Fellows, and V. Raman, An improved fixed parameter algorithm for vertex cover, Information Processing Letters 65, (1998), pp. 163\u2013168.","journal-title":"Information Processing Letters"},{"key":"7_CR2","unstructured":"R. Beigel and D. Eppstein, 3-coloring in time O(1.3446n): a no-MIS algorithm, Proc. 36th IEEE Symp. on Foundations of Computer Science, (1995), pp. 444\u2013452."},{"key":"7_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/3-540-46784-X_30","volume-title":"Vertex cover: further observations and further improvement","author":"J. Chen","year":"1999","unstructured":"J. Chen, I. A. Kanj, and W. Jia, Vertex cover: further observations and further improvement, Lecture Notes in Computer Science 1665 (WG\u201999), (1999pp. 313\u2013324."},{"key":"7_CR4","unstructured":"DIMACS Workshop on Faster Exact Solutions for NP-Hard Problems, Princeton, February 23\u201324, 2000."},{"key":"7_CR5","unstructured":"R. G. Downey, M. R. Fellows, and U. Stege, Parameterized complexity: A framework for systematically confronting computational intractability, AMS-DIMACS Proceedings Series 49, F. Roberts, J. Kratochvil, and J. Nesetril, eds., (1999), pp. 49\u201399."},{"key":"7_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/3-540-48340-3_35","volume-title":"An efficient exact algorithm for constraint bipartite vertex cover","author":"H. Fernau","year":"1999","unstructured":"H. Fernau and R. Niedermeier, An efficient exact algorithm for constraint bipartite vertex cover, Lecture Notes in Computer Science 1672 (MFCS\u201999), (1999), pp. 387\u2013397."},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"N. Hasan and C. L. Liu, Minimum fault coverage in reconfigurable arrays, Proc. 18th Int. Symp. on Fault-Tolerant Computing (FTCS\u201988), (1988), pp. 348\u2013353.","DOI":"10.1109\/FTCS.1988.5342"},{"key":"7_CR8","unstructured":"L. Lov\u00e1sz and M. D. Plummer, Matching Theory, Annals of Discrete Mathematics 29, North-Holland, 1986."},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1109\/12.509914","volume":"45","author":"C. P. Low","year":"1996","unstructured":"C. P. Low and H. W. Leong, A new class of efficient algorithms for reconfiguration of memory arrays, IEEE Trans. Comput. 45, (1996), pp. 614\u2013618.","journal-title":"IEEE Trans. Comput."},{"key":"7_CR10","unstructured":"S. Micali and V. Vazirani, An \n                  \n                    \n                  \n                  $$\nO\\left( {\\sqrt {|V|}  \\cdot |E|} \\right)\n$$\n                \n algorithm for finding maximum matching in general graphs, Proc. 21st IEEE Symp. on the Foundation of Computer Science, (1980), pp. 17\u201327."},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G. L. Nemhauser","year":"1975","unstructured":"G. L. Nemhauser and L. E. Trotter, Vertex packing: structural properties and algorithms, Mathematical Programming 8, (1975), pp. 232\u2013248.","journal-title":"Mathematical Programming"},{"key":"7_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume-title":"Upper bounds for vertex cover further improved","author":"R. Niedermeier","year":"1999","unstructured":"R. Niedermeier and P. Rossmanith, Upper bounds for vertex cover further improved, Lecture Notes in Computer Science 1563 (STACS\u201999), (1999), pp. 561\u2013570."},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(00)00004-1","volume":"73","author":"R. Niedermeier","year":"2000","unstructured":"R. Niedermeier and P. Rossmanith, A general method to speed up fixedparameter-tractable algorithms, Information Processing Letters 73, (2000), pp. 125\u2013129.","journal-title":"Information Processing Letters"},{"key":"7_CR14","unstructured":"N. J. Nilsson, Principles of Artificial Intelligence, Tioga Publishing Co., 1980."},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"R. Paturi, P. Pudlak, M. E. Saks, and F. Zane, An improved exponential-time algorithm for k-SAT, Proc. 39th IEEE Symp. on Foundations of Computer Science, (1998), pp. 628\u2013637.","DOI":"10.1109\/SFCS.1998.743513"},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"1153","DOI":"10.1109\/43.160001","volume":"11","author":"W. Shi","year":"1992","unstructured":"W. Shi and W. K. Fuchs, Probabilistic analysis and algorithms for reconfiguration of memory arrays, IEEE Trans. Computer-Aided Design 11, (1992), pp. 1153\u20131160.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/12.481492","volume":"45","author":"M. D. Smith","year":"1996","unstructured":"M. D. Smith and P. Mazumder, Generation of minimal vertex cover for row\/column allocation in self-repairable arrays, IEEE Trans. Comput. 45, (1996), pp. 109\u2013115.","journal-title":"IEEE Trans. Comput."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45477-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T22:44:07Z","timestamp":1550789047000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45477-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540427070","9783540454779"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-45477-2_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}