{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:55:09Z","timestamp":1740099309264,"version":"3.37.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030226282"},{"type":"electronic","value":"9783030226299"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-22629-9_20","type":"book-chapter","created":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:02:42Z","timestamp":1560283362000},"page":"279-294","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On $$(1+\\varepsilon )$$ -approximate Data Reduction for the Rural Postman Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4805-218X","authenticated-orcid":false,"given":"Ren\u00e9","family":"van Bevern","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2203-4386","authenticated-orcid":false,"given":"Till","family":"Fluschnik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9570-8519","authenticated-orcid":false,"given":"Oxana Yu.","family":"Tsidulko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,6,12]]},"reference":[{"issue":"12","key":"20_CR1","doi-asserted-by":"publisher","first-page":"3363","DOI":"10.1016\/j.cor.2005.02.009","volume":"33","author":"JM Belenguer","year":"2006","unstructured":"Belenguer, J.M., Benavent, E., Lacomme, P., Prins, C.: Lower and upper bounds for the mixed capacitated arc routing problem. Comput. Oper. Res. 33(12), 3363\u20133383 (2006)","journal-title":"Comput. Oper. Res."},{"key":"20_CR2","unstructured":"van Bevern, R., Fluschnik, T., Tsidulko, O.Yu.: Parameterized algorithms and data reduction for safe convoy routing. In: Proceedings of 18th ATMOS, OASIcs, vol. 65, pp. 10:1\u201310:19. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"issue":"4","key":"20_CR3","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/j.orl.2014.05.002","volume":"42","author":"R Bevern van","year":"2014","unstructured":"van Bevern, R., Hartung, S., Nichterlein, A., Sorge, M.: Constant-factor approximations for capacitated arc routing without triangle inequality. Oper. Res. Lett. 42(4), 290\u2013292 (2014)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"20_CR4","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1002\/net.21742","volume":"70","author":"R Bevern van","year":"2017","unstructured":"van Bevern, R., Komusiewicz, C., Sorge, M.: A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: theory and experiments. Networks 70(3), 262\u2013278 (2017)","journal-title":"Networks"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"van Bevern, R., Niedermeier, R., Sorge, M., Weller, M.: Complexity of arc routing problems. In: Arc Routing: Problems, Methods, and Applications, MOS-SIAM Series on Optimization, vol. 20. SIAM (2014)","DOI":"10.1137\/1.9781611973679.ch2"},{"issue":"4","key":"20_CR6","doi-asserted-by":"publisher","first-page":"1112","DOI":"10.1016\/j.cor.2006.07.007","volume":"35","author":"J Brand\u00e3o","year":"2008","unstructured":"Brand\u00e3o, J., Eglese, R.: A deterministic tabu search algorithm for the capacitated arc routing problem. Comput. Oper. Res. 35(4), 1112\u20131126 (2008)","journal-title":"Comput. Oper. Res."},{"volume-title":"Arc Routing: Problems, Methods, and Applications","year":"2014","key":"20_CR7","unstructured":"Corber\u00e1n, \u00c1., Laporte, G. (eds.): Arc Routing: Problems, Methods, and Applications. SIAM, Philadelphia (2014)"},{"key":"20_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). \n                      https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"1","key":"20_CR9","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1137\/110834810","volume":"27","author":"F Dorn","year":"2013","unstructured":"Dorn, F., Moser, H., Niedermeier, R., Weller, M.: Efficient algorithms for Eulerian extension and Rural Postman. SIAM J. Discrete Math. 27(1), 75\u201394 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5, 88\u2013124 (1973)","journal-title":"Math. Program."},{"key":"20_CR11","unstructured":"Eiben, E., Hermelin, D., Ramanujan, M.S.: Lossy kernels for hitting subgraphs. In: Proceedings of 42nd MFCS, LIPIcs, vol. 83, pp. 67:1\u201367:14. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2017)"},{"key":"20_CR12","unstructured":"Eiben, E., Kumar, M., Mouawad, A.E., Panolan, F., Siebertz, S.: Lossy kernels for connected dominating set on sparse graphs. In: Proceedings of 35th STACS, LIPIcs, vol. 96, pp. 29:1\u201329:15. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"issue":"3","key":"20_CR13","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1287\/opre.43.3.399","volume":"43","author":"HA Eiselt","year":"1995","unstructured":"Eiselt, H.A., Gendreau, M., Laporte, G.: Arc routing problems, Part II: The Rural Postman Problem. Oper. Res. 43(3), 399\u2013414 (1995)","journal-title":"Oper. Res."},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2016.06.004","volume":"84","author":"M Etscheid","year":"2017","unstructured":"Etscheid, M., Kratsch, S., Mnich, M., R\u00f6glin, H.: Polynomial kernels for weighted problems. J. Comput. Syst. Sci. 84, 1\u201310 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"20_CR15","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.jcss.2017.11.001","volume":"93","author":"MR Fellows","year":"2018","unstructured":"Fellows, M.R., Kulik, A., Rosamond, F.A., Shachnai, H.: Parameterized approximation via fidelity preserving transformations. J. Comput. Syst. Sci. 93, 30\u201340 (2018)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"20_CR16","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49\u201365 (1987)","journal-title":"Combinatorica"},{"issue":"8","key":"20_CR17","doi-asserted-by":"publisher","first-page":"945","DOI":"10.1057\/palgrave.jors.2601161","volume":"52","author":"G Ghiani","year":"2001","unstructured":"Ghiani, G., Improta, G.: The laser-plotter beam routing problem. J. Oper. Res. Soc. 52(8), 945\u2013951 (2001)","journal-title":"J. Oper. Res. Soc."},{"issue":"4","key":"20_CR18","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1002\/(SICI)1097-0037(199912)34:4<291::AID-NET9>3.0.CO;2-4","volume":"34","author":"G Ghiani","year":"1999","unstructured":"Ghiani, G., Laporte, G.: Eulerian location problems. Networks 34(4), 291\u2013302 (1999)","journal-title":"Networks"},{"issue":"3","key":"20_CR19","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1002\/net.3230110308","volume":"11","author":"BL Golden","year":"1981","unstructured":"Golden, B.L., Wong, R.T.: Capacitated arc routing problems. Networks 11(3), 305\u2013315 (1981)","journal-title":"Networks"},{"issue":"1","key":"20_CR20","first-page":"61","volume":"35","author":"M Gr\u00f6tschel","year":"1991","unstructured":"Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: Optimal control of plotting and drilling machines: a case study. Z. Oper. Res. 35(1), 61\u201384 (1991)","journal-title":"Z. Oper. Res."},{"issue":"1","key":"20_CR21","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News 38(1), 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"issue":"1","key":"20_CR22","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.jcss.2016.06.001","volume":"83","author":"G Gutin","year":"2017","unstructured":"Gutin, G., Wahlstr\u00f6m, M., Yeo, A.: Rural Postman parameterized by the number of components of required edges. J. Comput. Syst. Sci. 83(1), 121\u2013131 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"20_CR23","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1007\/s00453-014-9910-8","volume":"71","author":"D Hermelin","year":"2015","unstructured":"Hermelin, D., Kratsch, S., So\u0142tys, K., Wahlstr\u00f6m, M., Wu, X.: A completeness theory for polynomial (Turing) kernelization. Algorithmica 71(3), 702\u2013730 (2015)","journal-title":"Algorithmica"},{"issue":"3","key":"20_CR24","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/net.3230230304","volume":"23","author":"K Jansen","year":"1993","unstructured":"Jansen, K.: Bounds for the general capacitated routing problem. Networks 23(3), 165\u2013173 (1993)","journal-title":"Networks"},{"issue":"8","key":"20_CR25","doi-asserted-by":"publisher","first-page":"1665","DOI":"10.1016\/j.jcss.2015.06.003","volume":"81","author":"M Karpinski","year":"2015","unstructured":"Karpinski, M., Lampis, M., Schmied, R.: New inapproximability bounds for TSP. J. Comput. Syst. Sci. 81(8), 1665\u20131677 (2015)","journal-title":"J. Comput. Syst. Sci."},{"key":"20_CR26","unstructured":"Kratsch, S.: Recent developments in kernelization: A survey. Bull. EATCS 113 (2014)"},{"issue":"8","key":"20_CR27","doi-asserted-by":"publisher","first-page":"1690","DOI":"10.1007\/s00224-017-9837-y","volume":"62","author":"R Krithika","year":"2018","unstructured":"Krithika, R., Majumdar, D., Raman, V.: Revisiting connected vertex cover: FPT algorithms and lossy kernels. Theor. Comput. Syst. 62(8), 1690\u20131714 (2018)","journal-title":"Theor. Comput. Syst."},{"key":"20_CR28","unstructured":"Krithika, R., Misra, P., Rai, A., Tale, P.: Lossy kernels for graph contraction problems. In: Proceedings 36th FSTTCS, LIPIcs, vol. 65, pp. 23:1\u201323:14. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2016)"},{"key":"20_CR29","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Panolan, F., Ramanujan, M.S., Saurabh, S.: Lossy kernelization. In: Proceedings 49th STOC, pp. 224\u2013237. ACM (2017)","DOI":"10.1145\/3055399.3055456"},{"issue":"4","key":"20_CR30","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/2700210","volume":"11","author":"D Marx","year":"2015","unstructured":"Marx, D., V\u00e9gh, L.A.: Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation. ACM Trans. Algorithms 11(4), 27:1\u201327:24 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"20_CR31","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1002\/net.3230040105","volume":"4","author":"CS Orloff","year":"1974","unstructured":"Orloff, C.S.: A fundamental problem in vehicle routing. Networks 4(1), 35\u201364 (1974)","journal-title":"Networks"},{"key":"20_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-642-25870-1_28","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Sorge","year":"2011","unstructured":"Sorge, M., van Bevern, R., Niedermeier, R., Weller, M.: From few components to an Eulerian graph by adding arcs. In: Kolman, P., Kratochv\u00edl, J. (eds.) WG 2011. LNCS, vol. 6986, pp. 307\u2013318. Springer, Heidelberg (2011). \n                      https:\/\/doi.org\/10.1007\/978-3-642-25870-1_28"},{"key":"20_CR33","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.jda.2012.04.007","volume":"16","author":"M Sorge","year":"2012","unstructured":"Sorge, M., van Bevern, R., Niedermeier, R., Weller, M.: A new view on Rural Postman based on Eulerian extension and matching. J. Discrete Algorithms 16, 12\u201333 (2012)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"20_CR34","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0377-2217(85)90252-8","volume":"22","author":"G Ulusoy","year":"1985","unstructured":"Ulusoy, G.: The fleet size and mix problem for capacitated arc routing. Eur. J. Oper. Res. 22(3), 329\u2013337 (1985)","journal-title":"Eur. J. Oper. Res."},{"key":"20_CR35","doi-asserted-by":"publisher","first-page":"8","DOI":"10.2174\/1874243200802010008","volume":"2","author":"S W\u00f8hlk","year":"2008","unstructured":"W\u00f8hlk, S.: An approximation algorithm for the capacitated arc routing problem. Open Oper. Res. J. 2, 8\u201312 (2008)","journal-title":"Open Oper. Res. J."}],"container-title":["Lecture Notes in Computer Science","Mathematical Optimization Theory and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-22629-9_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:04:28Z","timestamp":1560283468000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-22629-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030226282","9783030226299"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-22629-9_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"MOTOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Mathematical Optimization Theory and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ekaterinburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"motor2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/motor2019.uran.ru","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}