{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T05:40:21Z","timestamp":1757310021236},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540357537"},{"type":"electronic","value":"9783540357551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11785293_32","type":"book-chapter","created":{"date-parts":[[2006,6,26]],"date-time":"2006-06-26T05:24:10Z","timestamp":1151299450000},"page":"339-350","source":"Crossref","is-referenced-by-count":5,"title":["Minimum Membership Set Covering and the Consecutive Ones Property"],"prefix":"10.1007","author":[{"given":"Michael","family":"Dom","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiong","family":"Guo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Wernicke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"32_CR1","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/0022-0000(80)90046-X","volume":"21","author":"G. Ausiello","year":"1980","unstructured":"Ausiello, G., D\u2019Atri, A., Protasi, M.: Structure preserving reductions among convex optimization problems. Journal of Computer and System Sciences\u00a021(1), 136\u2013153 (1980)","journal-title":"Journal of Computer and System Sciences"},{"key":"32_CR2","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":"32_CR3","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"key":"32_CR4","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1145\/1109557.1109577","volume-title":"Proc. 17th SODA","author":"E.D. Demaine","year":"2006","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Feige, U., Salavatipour, M.R.: Combination can be hard: approximability of the unique coverage problem. In: Proc. 17th SODA, pp. 162\u2013171. ACM Press, New York (2006)"},{"key":"32_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"issue":"4","key":"32_CR6","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S. Even","year":"1976","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput.\u00a05(4), 691\u2013703 (1976)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"32_CR7","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"32_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica\u00a018(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"Guo, J., Niedermeier, R.: Exact algorithms and applications for Tree-like Weighted Set Cover. Journal of Discrete Algorithms (to appear, 2006)","DOI":"10.1016\/j.jda.2005.07.005"},{"key":"32_CR10","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":"32_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)"},{"key":"32_CR12","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0166-218X(98)00078-X","volume":"88","author":"J. Meidanis","year":"1998","unstructured":"Meidanis, J., Porto, O., Telles, G.: On the consecutive ones property. Discrete Applied Mathematics\u00a088, 325\u2013354 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"32_CR13","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"G.L. Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, Chichester (1988)"},{"key":"32_CR14","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"32_CR15","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"issue":"2","key":"32_CR16","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., Sch\u00f6bel, A.: Set covering with almost consecutive ones property. Discrete Optimization\u00a01(2), 215\u2013228 (2004)","journal-title":"Discrete Optimization"},{"key":"32_CR17","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, 518\u2013532 (1962)","journal-title":"Operations Research"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11785293_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,4]],"date-time":"2024-02-04T23:31:13Z","timestamp":1707089473000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11785293_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540357537","9783540357551"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11785293_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}