{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T12:43:24Z","timestamp":1725453804809},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387678"},{"type":"electronic","value":"9783642387685"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38768-5_25","type":"book-chapter","created":{"date-parts":[[2013,5,17]],"date-time":"2013-05-17T00:31:28Z","timestamp":1368750688000},"page":"268-279","source":"Crossref","is-referenced-by-count":1,"title":["A Linear-Time Algorithm for the Minimum Degree Hypergraph Problem with the Consecutive Ones Property"],"prefix":"10.1007","author":[{"given":"Chih-Hsuan","family":"Li","sequence":"first","affiliation":[]},{"given":"Jhih-Hong","family":"Ye","sequence":"additional","affiliation":[]},{"given":"Biing-Feng","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","volume-title":"Private communication","author":"S. Alstrup","year":"2012","unstructured":"Alstrup, S.: Private communication (2012)"},{"key":"25_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/3-540-45022-X_8","volume-title":"Automata, Languages and Programming","author":"S. Alstrup","year":"2000","unstructured":"Alstrup, S., Holm, J.: Improved algorithms for finding level ancestors in dynamic trees. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 73\u201384. Springer, Heidelberg (2000)"},{"issue":"3","key":"25_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences\u00a013(3), 335\u2013379 (1976)","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1023\/A:1019225027893","volume":"98","author":"A. Caprara","year":"2000","unstructured":"Caprara, A., Toth, P., Fischetti, M.: Algorithms for the set covering problem. Annals of Operations Research\u00a098, 353\u2013371 (2000)","journal-title":"Annals of Operations Research"},{"key":"25_CR5","unstructured":"Carr, R.D., Doddi, S., Konjevod, G., Marathe, M.: On the red-blue set cover problem. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 345\u2013353 (2000)"},{"issue":"20","key":"25_CR6","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1016\/j.ipl.2010.07.010","volume":"110","author":"M.S. Chang","year":"2010","unstructured":"Chang, M.S., Chung, H.H., Lin, C.C.: An improved algorithm for the red-blue hitting set problem with the consecutive ones property. Information Processing Letters\u00a0110(20), 845\u2013848 (2010)","journal-title":"Information Processing Letters"},{"issue":"3","key":"25_CR7","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/j.jda.2007.11.002","volume":"6","author":"M. Dom","year":"2008","unstructured":"Dom, M., Guo, J., Niedermeier, R., Wernicke, S.: Red-blue covering problems and the consecutive ones property. Journal of Discrete Algorithms\u00a06(3), 393\u2013407 (2008)","journal-title":"Journal of Discrete Algorithms"},{"key":"25_CR8","unstructured":"Feder, T., Motwani, R., Zhu, A.: k-connected spanning subgraphs of low degree. Tech. Rep. TR06-041, Electronic Colloquium on Computational Complexity (2006)"},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/11533719_21","volume-title":"Computing and Combinatorics","author":"F. Kuhn","year":"2005","unstructured":"Kuhn, F., von Rickenbach, P., Wattenhofer, R., Welzl, E., Zollinger, A.: Interference in cellular networks: The minimum membership set cover problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 188\u2013198. Springer, Heidelberg (2005)"},{"key":"25_CR10","unstructured":"Mecke, S., Sch\u00f6bel, A., Wagner, D.: Station location - complexity and approximation. In: 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (2005)"},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1007\/978-3-540-30140-0_67","volume-title":"Algorithms \u2013 ESA 2004","author":"S. Mecke","year":"2004","unstructured":"Mecke, S., Wagner, D.: Solving geometric covering problems by data reduction. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 760\u2013771. Springer, Heidelberg (2004)"},{"issue":"2","key":"25_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.disopt.2004.07.002","volume":"1","author":"N. Ruf","year":"2004","unstructured":"Ruf, N., Schobel, A.: Set covering with almost consecutive ones property. Discrete Optimization\u00a01(2), 215\u2013228 (2004)","journal-title":"Discrete Optimization"},{"issue":"4","key":"25_CR13","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1287\/opre.10.4.518","volume":"10","author":"A.F. Veinott","year":"1962","unstructured":"Veinott, A.F., Wagner, H.M.: Optimal capacity scheduling. Operations Research\u00a010(4), 518\u2013532 (1962)","journal-title":"Operations Research"},{"key":"25_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-32241-9_15","volume-title":"Computing and Combinatorics","author":"B.F. Wang","year":"2012","unstructured":"Wang, B.F., Li, C.H.: On the minimum degree hypergraph problem with subset size two and the red-blue set cover problem with the consecutive ones property. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol.\u00a07434, pp. 169\u2013180. Springer, Heidelberg (2012)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38768-5_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T22:17:42Z","timestamp":1557699462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38768-5_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387678","9783642387685"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38768-5_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}