{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:35Z","timestamp":1740109295923,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T00:00:00Z","timestamp":1579910400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T00:00:00Z","timestamp":1579910400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004409","name":"Minist\u00e8re de l\u2019Enseignement Sup\u00e9rieur, de la Recherche Scientifique et des Technologies de l\u2019Information et de la Communication","doi-asserted-by":"publisher","award":["38593YJ"],"award-info":[{"award-number":["38593YJ"]}],"id":[{"id":"10.13039\/501100004409","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003388","name":"Minist\u00e8re des Affaires \u00c9trang\u00e8res","doi-asserted-by":"publisher","award":["38593YJ"],"award-info":[{"award-number":["38593YJ"]}],"id":[{"id":"10.13039\/501100003388","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["38593YJ","JP18K11168","JP18K11169","JP18H04091"],"award-info":[{"award-number":["38593YJ","JP18K11168","JP18K11169","JP18H04091"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE40-0028","ANR-17-CE40-0028"],"award-info":[{"award-number":["ANR-17-CE40-0028","ANR-17-CE40-0028"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s00453-020-00679-6","type":"journal-article","created":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T06:02:22Z","timestamp":1579932142000},"page":"1909-1938","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized Orientable Deletion"],"prefix":"10.1007","volume":"82","author":[{"given":"Tesshu","family":"Hanaka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0977-0154","authenticated-orcid":false,"given":"Ioannis","family":"Katsikarelis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Lampis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,25]]},"reference":[{"key":"679_CR1","unstructured":"Asahiro, Y., Jansson, J., Miyano, E., Ono, H.: Upper and lower degree bounded graph orientation with minimum penalty. In: Proceedings of the 18th Computing: The Australasian Theory Symposium, CATS 2012, volume 128 of CRPIT, pp. 139\u2013146 (2012)"},{"issue":"1","key":"679_CR2","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/s00224-014-9565-5","volume":"58","author":"Y Asahiro","year":"2016","unstructured":"Asahiro, Y., Jansson, J., Miyano, E., Ono, H.: Degree-constrained graph orientation: maximum satisfaction and minimum violation. Theory Comput. Syst. 58(1), 60\u201393 (2016)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"679_CR3","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/s10878-009-9276-z","volume":"22","author":"Y Asahiro","year":"2011","unstructured":"Asahiro, Y., Jansson, J., Miyano, E., Ono, H., Zenmyo, K.: Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree. J. Comb. Optim. 22(1), 78\u201396 (2011)","journal-title":"J. Comb. Optim."},{"issue":"7","key":"679_CR4","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/j.dam.2010.11.003","volume":"159","author":"Y Asahiro","year":"2011","unstructured":"Asahiro, Y., Miyano, E., Ono, H.: Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree. Discrete Appl. Math. 159(7), 498\u2013508 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"679_CR5","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1142\/S0129054107004644","volume":"18","author":"Y Asahiro","year":"2007","unstructured":"Asahiro, Y., Miyano, E., Ono, H., Zenmyo, K.: Graph orientation algorithms to minimize the maximum outdegree. Int. J. Found. Comput. Sci. 18(2), 197\u2013215 (2007)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"679_CR6","doi-asserted-by":"crossref","unstructured":"Bateni, M.H., Charikar, M., Guruswami, V.: Maxmin allocation via degree lower-bounded arborescences. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009. ACM, pp. 543\u2013552 (2009)","DOI":"10.1145\/1536414.1536488"},{"issue":"1\u20132","key":"679_CR7","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.dam.2011.08.013","volume":"160","author":"N Betzler","year":"2012","unstructured":"Betzler, N., Bredereck, R., Niedermeier, R., Uhlmann, J.: On bounded-degree vertex deletion parameterized by treewidth. Discrete Appl. Math. 160(1\u20132), 53\u201360 (2012)","journal-title":"Discrete Appl. Math."},{"key":"679_CR8","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S1571-0653(05)80116-7","volume":"5","author":"HL Bodlaender","year":"2000","unstructured":"Bodlaender, H.L.: The algorithmic theory of treewidth. Electron. Notes Discrete Math. 5, 27\u201330 (2000)","journal-title":"Electron. Notes Discrete Math."},{"key":"679_CR9","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Treewidth: characterizations, applications, and computations. In: Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006, volume 4271 of Lecture Notes in Computer Science, pp. 1\u201314 (2006)","DOI":"10.1007\/11917496_1"},{"issue":"3","key":"679_CR10","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3), 255\u2013269 (2008)","journal-title":"Comput. J."},{"issue":"7","key":"679_CR11","doi-asserted-by":"publisher","first-page":"2160","DOI":"10.1007\/s00453-017-0399-9","volume":"80","author":"HL Bodlaender","year":"2018","unstructured":"Bodlaender, H.L., Ono, H., Otachi, Y.: Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity. Algorithmica 80(7), 2160\u20132180 (2018)","journal-title":"Algorithmica"},{"key":"679_CR12","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.dam.2017.10.018","volume":"236","author":"HL Bodlaender","year":"2018","unstructured":"Bodlaender, H.L., Ono, H., Otachi, Y.: A faster parameterized algorithm for pseudoforest deletion. Discrete Appl. Math. 236, 42\u201356 (2018)","journal-title":"Discrete Appl. Math."},{"key":"679_CR13","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Chuzhoy, J., Khanna, S.: On allocating goods to maximize fairness. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009. IEEE Computer Society, pp. 107\u2013116 (2009)","DOI":"10.1109\/FOCS.2009.51"},{"issue":"2","key":"679_CR14","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0304-3975(91)90020-3","volume":"86","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci. 86(2), 243\u2013266 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"679_CR15","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic\u2014A Language-Theoretic Approach, volume 138 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press (2012)","DOI":"10.1017\/CBO9780511977619"},{"issue":"2","key":"679_CR16","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"key":"679_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"1","key":"679_CR18","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/s00453-012-9668-9","volume":"68","author":"T Ebenlendr","year":"2014","unstructured":"Ebenlendr, T., Krc\u00e1l, M., Sgall, J.: Graph balancing: a special case of scheduling unrelated parallel machines. Algorithmica 68(1), 62\u201380 (2014)","journal-title":"Algorithmica"},{"issue":"4","key":"679_CR19","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"679_CR20","first-page":"13:1","volume":"14","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms 14(2), 13:1\u201313:30 (2018)","journal-title":"ACM Trans. Algorithms"},{"issue":"34\u201336","key":"679_CR21","doi-asserted-by":"publisher","first-page":"3181","DOI":"10.1016\/j.tcs.2010.05.015","volume":"411","author":"L Mathieson","year":"2010","unstructured":"Mathieson, L.: The parameterized complexity of editing graphs for bounded degeneracy. Theor. Comput. Sci. 411(34\u201336), 3181\u20133187 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"679_CR22","doi-asserted-by":"publisher","first-page":"221","DOI":"10.4086\/toc.2015.v011a007","volume":"11","author":"D Moshkovitz","year":"2015","unstructured":"Moshkovitz, D.: The projection games conjecture and the NP-hardness of $$\\ln n$$-approximating set-cover. Theory Comput. 11, 221\u2013235 (2015)","journal-title":"Theory Comput."},{"issue":"2","key":"679_CR23","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1137\/16M1100794","volume":"32","author":"G Philip","year":"2018","unstructured":"Philip, G., Rai, A., Saurabh, S.: Generalized pseudoforest deletion: algorithms and uniform kernel. SIAM J. Discrete Math. 32(2), 882\u2013901 (2018)","journal-title":"SIAM J. Discrete Math."},{"key":"679_CR24","unstructured":"Szeider, S.: Not so easy problems for tree decomposable graphs. CoRR arXiv:1107.1177 (2011)"},{"issue":"2","key":"679_CR25","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0304-3975(94)00160-K","volume":"137","author":"A Takahashi","year":"1995","unstructured":"Takahashi, A., Ueno, S., Kajitani, Y.: Mixed searching and proper-path-width. Theoret. Comput. Sci. 137(2), 253\u2013268 (1995)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"679_CR26","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s10951-013-0359-4","volume":"17","author":"J Verschae","year":"2014","unstructured":"Verschae, J., Wiese, A.: On the configuration-LP for scheduling on unrelated machines. J. Sched. 17(4), 371\u2013383 (2014)","journal-title":"J. Sched."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00679-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00679-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00679-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,12]],"date-time":"2022-10-12T21:43:33Z","timestamp":1665611013000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00679-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,25]]},"references-count":26,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["679"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00679-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,1,25]]},"assertion":[{"value":"10 August 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}