{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:11:58Z","timestamp":1773655918595,"version":"3.50.1"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,3,22]],"date-time":"2008-03-22T00:00:00Z","timestamp":1206144000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,2]]},"DOI":"10.1007\/s00224-008-9107-0","type":"journal-article","created":{"date-parts":[[2008,3,21]],"date-time":"2008-03-21T10:58:30Z","timestamp":1206097110000},"page":"215-229","source":"Crossref","is-referenced-by-count":3,"title":["The Ferry Cover Problem"],"prefix":"10.1007","volume":"44","author":[{"given":"Michael","family":"Lampis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valia","family":"Mitsou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,3,22]]},"reference":[{"key":"9107_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and intractability of approximation problems. In: Proc. 33rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp.\u00a013\u201322 (1992)","DOI":"10.1109\/SFCS.1992.267823"},{"key":"9107_CR2","series-title":"The Mathematical Arts","first-page":"379","volume-title":"Charlemagne and His Heritage: 1200 Years of Civilization and Science in Europe","author":"R. Bornd\u00f6rfer","year":"1998","unstructured":"Bornd\u00f6rfer, R., Gr\u00f6tschel, M., L\u00f6bel, A.: Alcuin\u2019s transportation problems and integer programming. In: Butzeretal, P.L., et al. (eds.) Charlemagne and His Heritage: 1200 Years of Civilization and Science in Europe. The Mathematical Arts, vol.\u00a02, pp. 379\u2013409. Brepols, Turnhout (1998)"},{"key":"9107_CR3","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9107_CR4","doi-asserted-by":"crossref","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. In: ACM Symposium on Theory of Computing, pp.\u00a0698\u2013707 (1993)","DOI":"10.1145\/167088.167266"},{"issue":"1","key":"9107_CR5","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/PL00009810","volume":"18","author":"M.X. Goemans","year":"1998","unstructured":"Goemans, M.X., Williamson, D.P.: Primal-dual approximation algorithms for feedback problems in planar graphs. Combinatorica 18(1), 37\u201359 (1998)","journal-title":"Combinatorica"},{"issue":"1","key":"9107_CR6","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of h-coloring. J.\u00a0Comb. Theory Ser. B 48(1), 92\u2013110 (1990)","journal-title":"J.\u00a0Comb. Theory Ser. B"},{"issue":"3","key":"9107_CR7","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9107_CR8","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1145\/800133.804355","volume-title":"STOC \u201978: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing","author":"M. Yannakakis","year":"1978","unstructured":"Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: STOC \u201978: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 253\u2013264. ACM, New York (1978)"},{"key":"9107_CR9","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9107-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9107-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9107-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:35Z","timestamp":1558684295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9107-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,22]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,2]]}},"alternative-id":["9107"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9107-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3,22]]}}}