{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:13Z","timestamp":1740109273046,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2017,12,5]],"date-time":"2017-12-05T00:00:00Z","timestamp":1512432000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,12,5]],"date-time":"2017-12-05T00:00:00Z","timestamp":1512432000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001700","name":"Ministry of Education, Culture, Sports, Science and Technology","doi-asserted-by":"crossref","award":["KAKENHI 24106004","KAKENHI 24106004"],"award-info":[{"award-number":["KAKENHI 24106004","KAKENHI 24106004"]}],"id":[{"id":"10.13039\/501100001700","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["KAKENHI 24220003","KAKENHI 25730003"],"award-info":[{"award-number":["KAKENHI 24220003","KAKENHI 25730003"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["KAKENHI 26540005"],"award-info":[{"award-number":["KAKENHI 26540005"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00453-017-0399-9","type":"journal-article","created":{"date-parts":[[2017,12,5]],"date-time":"2017-12-05T15:25:35Z","timestamp":1512487535000},"page":"2160-2180","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity"],"prefix":"10.1007","volume":"80","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Hirotaka","family":"Ono","sequence":"additional","affiliation":[]},{"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,5]]},"reference":[{"issue":"2","key":"399_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"399_CR2","unstructured":"Asahiro, Y., Jansson, J., Miyano, E., Ono, H.: Upper and lower degree bounded graph orientation with minimum penalty. In Eighteenth Computing: The Australasian Theory Symposium, CATS 2012, vol. 128 of CRPIT, pp. 139\u2013146. Australian Computer Society (2012)"},{"issue":"1","key":"399_CR3","doi-asserted-by":"publisher","first-page":"441","DOI":"10.7155\/jgaa.00371","volume":"19","author":"Y Asahiro","year":"2015","unstructured":"Asahiro, Y., Jansson, J., Miyano, E., Ono, H.: Graph orientations optimizing the number of light or heavy vertices. J. Graph Algorithms Appl. 19(1), 441\u2013465 (2015)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"399_CR4","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":"399_CR5","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":"2","key":"399_CR6","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":"399_CR7","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1016\/j.endm.2015.06.076","volume":"49","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Heggernes, P., Telle, J.A.: Recognizability equals definability for graphs of bounded treewidth and bounded chordality. Electr. Notes Discrete Math. 49, 559\u2013568 (2015)","journal-title":"Electr. Notes Discrete Math."},{"issue":"5","key":"399_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00008","volume":"2","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D., M\u00fcller, H.: Treewidth and minimum fill-in on $$d$$-trapezoid graphs. J. Graph Algorithms Appl. 2(5), 1\u201323 (1998)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1\u20132","key":"399_CR9","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","volume":"276","author":"V Bouchitt\u00e9","year":"2002","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theor. Comput. Sci. 276(1\u20132), 17\u201332 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"399_CR10","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."},{"issue":"4","key":"399_CR11","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1002\/net.3230150409","volume":"15","author":"FRK Chung","year":"1985","unstructured":"Chung, F.R.K., Garey, M.R., Tarjan, R.E.: Strongly connected orientations of mixed multigraphs. Networks 15(4), 477\u2013484 (1985)","journal-title":"Networks"},{"issue":"4","key":"399_CR12","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"DG Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825\u2013847 (2005)","journal-title":"SIAM J. Comput."},{"key":"399_CR13","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1051\/ita\/1992260302571","volume":"26","author":"B Courcelle","year":"1992","unstructured":"Courcelle, B.: The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues. Theor. Inform. Appl. 26, 257\u2013286 (1992)","journal-title":"Theor. Inform. Appl."},{"issue":"2","key":"399_CR14","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0168-0072(95)94698-V","volume":"72","author":"B Courcelle","year":"1995","unstructured":"Courcelle, B.: The monadic second-order logic of graphs VIII: orientations. Ann. Pure Appl. Logic 72(2), 103\u2013143 (1995)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"2","key":"399_CR15","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."},{"issue":"1\u20133","key":"399_CR16","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"key":"399_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":"2","key":"399_CR18","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1137\/070687256","volume":"23","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-complete. SIAM J. Discrete Math. 23(2), 909\u2013939 (2009)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"399_CR19","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/140964801","volume":"44","author":"FV Fomin","year":"2015","unstructured":"Fomin, F.V., Todinca, I., Villanger, Y.: Large induced subgraphs via triangulations and CMSO. SIAM J. Comput. 44(1), 54\u201387 (2015)","journal-title":"SIAM J. Comput."},{"key":"399_CR20","unstructured":"Frank, A., Gy\u00e1rf\u00e1s, A.: How to orient the edges of a graph? In: Combinatorics (Proceedings of the 5th Hungarian Combinatorial Colloquium, Keszthely, 1976), vol.\u00a018 of Colloquia mathematica Societatis Janos Bolyai, pp. 353\u2013364 (1978)"},{"key":"399_CR21","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: Upper degree-constrained partial orientations. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pp. 554\u2013563 (2006)","DOI":"10.1145\/1109557.1109618"},{"key":"399_CR22","doi-asserted-by":"crossref","unstructured":"Gaspers, S., Kratsch, D., Liedloff, M., Todinca, I.: Exponential time algorithms for the minimum dominating set problem on some graph classes. ACM Trans. Algorithms 6, Article No. 9 (2009)","DOI":"10.1145\/1644015.1644024"},{"key":"399_CR23","doi-asserted-by":"crossref","unstructured":"Gurski, F., Wanke, E.: The tree-width of clique-width bounded graphs without $$K_{n,n}$$. In: Graph-Theoretic Concepts in Computer Science, 26th International Workshop, WG 2000, vol. 1928 of Lecture Notes in Computer Science, pp. 196\u2013205 (2000)","DOI":"10.1007\/3-540-40064-8_19"},{"issue":"1","key":"399_CR24","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01462229","volume":"11","author":"M Habib","year":"1994","unstructured":"Habib, M., M\u00f6hring, R.H.: Treewidth of cocomparability graphs and a new order-theoretic parameter. Order 11(1), 47\u201360 (1994)","journal-title":"Order"},{"issue":"4","key":"399_CR25","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/0016-0032(65)90340-6","volume":"279","author":"SL Hakimi","year":"1965","unstructured":"Hakimi, S.L.: On the degrees of the vertices of a directed graph. J. Franklin Inst. 279(4), 290\u2013308 (1965)","journal-title":"J. Franklin Inst."},{"key":"399_CR26","unstructured":"Heggernes, P.: Treewidth, partial $$k$$-trees, and chordal graphs. Partial curriculum in INF334\u2014advanced algorithmical techniques, Department of Informatics, University of Bergen, Norway (2005)"},{"key":"399_CR27","unstructured":"Jaffke, L., Bodlaender, H.L.: Definability equals recognizability for k-outerplanar graphs. In: 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16\u201318, 2015, Patras, Greece, vol.\u00a043 of LIPIcs, pp. 175\u2013186 (2015)"},{"key":"399_CR28","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.dam.2015.05.007","volume":"194","author":"K Khoshkhah","year":"2015","unstructured":"Khoshkhah, K.: On finding orientations with the fewest number of vertices with small out-degree. Discrete Appl. Math. 194, 163\u2013166 (2015)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"399_CR29","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci. 289(2), 997\u20131008 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"399_CR30","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1006\/jagm.1995.1037","volume":"19","author":"T Kloks","year":"1995","unstructured":"Kloks, T., Kratsch, D.: Treewidth of chordal bipartite graphs. J. Algorithms 19(2), 266\u2013281 (1995)","journal-title":"J. Algorithms"},{"issue":"2","key":"399_CR31","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1006\/jagm.1998.0936","volume":"28","author":"T Kloks","year":"1998","unstructured":"Kloks, T., Kratsch, D., Wong, C.K.: Minimum fill-in on circle and circular-arc graphs. J. Algorithms 28(2), 272\u2013289 (1998)","journal-title":"J. Algorithms"},{"key":"399_CR32","unstructured":"Kloks, T., Liu, C.-H., Poon, S.-H.: Feedback vertex set on chordal bipartite graphs. CoRR, \n                    arXiv:1104.3915\n                    \n                   (2011)"},{"issue":"3","key":"399_CR33","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1007\/s00453-014-9871-y","volume":"72","author":"A Kosowski","year":"2015","unstructured":"Kosowski, A., Li, B., Nisse, N., Suchan, K.: $$k$$-chordal graphs: from cops and robber to compact routing via treewidth. Algorithmica 72(3), 758\u2013777 (2015)","journal-title":"Algorithmica"},{"key":"399_CR34","unstructured":"Kratsch, D.: The Structure of Graphs and the Design of Efficient Algorithms. Habilitation thesis, Friedrich-Schiller-University of Jena, Germany (1996)"},{"issue":"2","key":"399_CR35","first-page":"143","volume":"15","author":"HG Landau","year":"1953","unstructured":"Landau, H.G.: On dominance relations and the structure of animal societies: III the condition for a score structure. Bull. Math. Biol. 15(2), 143\u2013148 (1953)","journal-title":"Bull. Math. Biol."},{"issue":"1","key":"399_CR36","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"CG Lekkerkerker","year":"1962","unstructured":"Lekkerkerker, C.G., Boland, J.C.: Representation of a finite graph by a set of intervals on the real line. Fund. Math. 51(1), 45\u201364 (1962)","journal-title":"Fund. Math."},{"issue":"34\u201336","key":"399_CR37","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."},{"issue":"3","key":"399_CR38","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"DW Matula","year":"1983","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417\u2013427 (1983)","journal-title":"J. ACM"},{"key":"399_CR39","unstructured":"Milani\u010d, M.: Algorithmic developments and complexity results for finding maximum and exact independent sets in graphs. Ph.D. thesis, Rutgers University (2007)"},{"key":"399_CR40","doi-asserted-by":"publisher","first-page":"555","DOI":"10.4153\/CJM-1960-049-6","volume":"12","author":"CSJA Nash-Williams","year":"1960","unstructured":"Nash-Williams, C.S.J.A.: On orientations, connectivity and odd vertex pairings in finite graphs. Canad. J. Math 12, 555\u2013567 (1960)","journal-title":"Canad. J. Math"},{"key":"399_CR41","doi-asserted-by":"crossref","unstructured":"Oum, S.-I.: Approximating rank-width and clique-width quickly. ACM Trans. Algorithms 5, Article No. 10 (2008)","DOI":"10.1145\/1435375.1435385"},{"key":"399_CR42","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S Oum","year":"2006","unstructured":"Oum, S., Seymour, P.D.: Approximating clique-width and branch-width. J. Comb. Theory Ser. B 96, 514\u2013528 (2006)","journal-title":"J. Comb. Theory Ser. B"},{"key":"399_CR43","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M., Pilipczuk, M.: Finding a maximum induced degenerate subgraph faster than $$2^{n}$$. In: Parameterized and Exact Computation\u20147th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12\u201314, 2012. Proceedings, vol. 7535 of Lecture Notes in Computer Science, pp. 3\u201312 (2012)","DOI":"10.1007\/978-3-642-33293-7_3"},{"issue":"5","key":"399_CR44","doi-asserted-by":"publisher","first-page":"281","DOI":"10.2307\/2303897","volume":"46","author":"HE Robbins","year":"1939","unstructured":"Robbins, H.E.: A theorem on graphs, with an application to a problem of traffic control. Am. Math. Mon. 46(5), 281\u2013283 (1939)","journal-title":"Am. Math. Mon."},{"key":"399_CR45","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Berlin (2003)"},{"issue":"2","key":"399_CR46","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0012-365X(73)90108-8","volume":"5","author":"RP Stanley","year":"1973","unstructured":"Stanley, R.P.: Acyclic orientations of graphs. Discrete Math. 5(2), 171\u2013178 (1973)","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"399_CR47","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/j.dam.2003.07.007","volume":"143","author":"V Venkateswaran","year":"2004","unstructured":"Venkateswaran, V.: Minimizing maximum indegree. Discrete Appl. Math. 143(1\u20133), 374\u2013378 (2004)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0399-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0399-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0399-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:28:57Z","timestamp":1589696937000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0399-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,5]]},"references-count":47,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["399"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0399-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,12,5]]},"assertion":[{"value":"29 January 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 December 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}