{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T14:40:06Z","timestamp":1736520006707,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540359043"},{"type":"electronic","value":"9783540359050"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_38","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T10:46:45Z","timestamp":1151491605000},"page":"431-442","source":"Crossref","is-referenced-by-count":0,"title":["How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover"],"prefix":"10.1007","author":[{"given":"Toshihiro","family":"Fujito","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"38_CR1","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0020-0190(93)90072-H","volume":"47","author":"E.M. Arkin","year":"1993","unstructured":"Arkin, E.M., Halld\u00f3rsson, M.M., Hassin, R.: Approximating the tree and tour covers of a graph. Inform. Process. Lett.\u00a047, 275\u2013282 (1993)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"38_CR2","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s004530010009","volume":"27","author":"R. Bar-Yehuda","year":"2000","unstructured":"Bar-Yehuda, R.: One for the price of two: A unified approach for approximating covering problems. Algorithmica\u00a027(2), 131\u2013144 (2000)","journal-title":"Algorithmica"},{"key":"38_CR3","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics\u00a025, 27\u201346 (1985)","journal-title":"Annals of Discrete Mathematics"},{"issue":"3","key":"38_CR4","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/050625382","volume":"19","author":"R. Bar-Yehuda","year":"2005","unstructured":"Bar-Yehuda, R., Rawitz, D.: On the equivalence between the primal-dual schema and the local ratio technique. SIAM J. Discrete Math.\u00a019(3), 762\u2013797 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"38_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0167-6377(98)00021-2","volume":"22","author":"F.A. Chudak","year":"1998","unstructured":"Chudak, F.A., Goemans, M.X., Hochbaum, D.S., Williamson, D.P.: A primal-dual interpretation of recent 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett.\u00a022, 111\u2013118 (1998)","journal-title":"Oper. Res. Lett."},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"Dinur, I., Safra, S.: The importance of being biased. In: Proc. 34th ACM Symp. Theory of Computing, pp. 33\u201342 (2002)","DOI":"10.1145\/509907.509915"},{"key":"38_CR7","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71","author":"J. Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Nat. Bur. Standards B\u00a071, 233\u2013240 (1967)","journal-title":"J. Res. Nat. Bur. Standards B"},{"issue":"6","key":"38_CR8","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0020-0190(01)00138-7","volume":"79","author":"T. Fujito","year":"2001","unstructured":"Fujito, T.: On approximability of the independent\/connected edge dominating set problems. Inform. Process. Lett.\u00a079(6), 261\u2013266 (2001)","journal-title":"Inform. Process. Lett."},{"key":"38_CR9","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0166-218X(00)00383-8","volume":"118","author":"T. Fujito","year":"2002","unstructured":"Fujito, T., Nagamochi, H.: A 2-approximation algorithm for the minimum weight edge dominating set problem. Discrete Appl. Math.\u00a0118, 199\u2013207 (2002)","journal-title":"Discrete Appl. Math."},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01580218","volume":"6","author":"D.R. Fulkerson","year":"1974","unstructured":"Fulkerson, D.R.: Packing rooted directed cuts in a weighted directed graph. Math. Programming\u00a06, 1\u201313 (1974)","journal-title":"Math. Programming"},{"issue":"4","key":"38_CR11","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner-tree problem is NP-complete. SIAM J. Appl. Math.\u00a032(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"issue":"5","key":"38_CR12","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E. Halperin","year":"2002","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput.\u00a031(5), 1608\u20131623 (2002)","journal-title":"SIAM J. Comput."},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. In: Proc. 18th IEEE Conf. Computational Complexity, pp. 379\u2013386 (2003)","DOI":"10.1109\/CCC.2003.1214437"},{"issue":"3","key":"38_CR14","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/s00453-003-1071-0","volume":"38","author":"J. K\u00f6nemann","year":"2003","unstructured":"K\u00f6nemann, J., Konjevod, G., Parekh, O., Sinha, A.: Improved approximations for tour and tree covers. Algorithmica\u00a038(3), 441\u2013449 (2003)","journal-title":"Algorithmica"},{"key":"38_CR15","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informat\u00a022, 115\u2013123 (1985)","journal-title":"Acta Informat"},{"key":"38_CR16","unstructured":"Parekh, O.: Edge dominating and hypomatchable sets. In: Proc. 13th ACM-SIAM Symp. Discrete Algorithms, pp. 287\u2013291 (2002)"},{"issue":"5","key":"38_CR17","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"C. Savage","year":"1982","unstructured":"Savage, C.: Depth-first search and the vertex cover problem. Inform. Process. Lett.\u00a014(5), 233\u2013235 (1982)","journal-title":"Inform. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T16:14:58Z","timestamp":1736439298000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11786986_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}