{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T09:31:30Z","timestamp":1742981490409,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031433795"},{"type":"electronic","value":"9783031433801"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-43380-1_18","type":"book-chapter","created":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T20:29:12Z","timestamp":1695414552000},"page":"246-260","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Degreewidth: A New Parameter for\u00a0Solving Problems on\u00a0Tournaments"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4203-5140","authenticated-orcid":false,"given":"Tom","family":"Davot","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1460-269X","authenticated-orcid":false,"given":"Lucas","family":"Isenmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3633-542X","authenticated-orcid":false,"given":"Sanjukta","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4550-8399","authenticated-orcid":false,"given":"Jocelyn","family":"Thiebaut","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,23]]},"reference":[{"issue":"4","key":"18_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33(4), 461\u2013493 (2002)","journal-title":"Algorithmica"},{"issue":"14","key":"18_CR2","doi-asserted-by":"publisher","first-page":"5638","DOI":"10.1073\/pnas.1014428108","volume":"108","author":"S Allesina","year":"2011","unstructured":"Allesina, S., Levine, J.M.: A competitive network theory of species diversity. Proc. Natl. Acad. Sci. 108(14), 5638\u20135642 (2011)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"1","key":"18_CR3","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1137\/050623905","volume":"20","author":"N Alon","year":"2006","unstructured":"Alon, N.: Ranking tournaments. SIAM J. Discret. Math. 20(1), 137\u2013142 (2006). https:\/\/doi.org\/10.1137\/050623905","journal-title":"SIAM J. Discret. Math."},{"key":"18_CR4","series-title":"Springer Monographs in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-998-1","volume-title":"Digraphs - Theory, Algorithms and Applications","author":"J Bang-Jensen","year":"2009","unstructured":"Bang-Jensen, J., Gutin, G.Z.: Digraphs - Theory, Algorithms and Applications. Springer Monographs in Mathematics, 2nd edn. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-1-84800-998-1","edition":"2"},{"issue":"4","key":"18_CR5","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1137\/S0097539796305109","volume":"27","author":"R Bar-Yehuda","year":"1998","unstructured":"Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM J. Comput. 27(4), 942\u2013959 (1998). https:\/\/doi.org\/10.1137\/S0097539796305109","journal-title":"SIAM J. Comput."},{"key":"18_CR6","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT. Electron. Colloquium Comput. Complex. (049) (2003). http:\/\/eccc.hpi-web.de\/eccc-reports\/2003\/TR03-049\/index.html"},{"key":"18_CR7","doi-asserted-by":"publisher","unstructured":"Bessy, S., et al.: Packing arc-disjoint cycles in tournaments. In: Rossmanith, P., Heggernes, P., Katoen, J. (eds.) 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, 26\u201330 August 2019, Aachen, Germany. LIPIcs, vol. 138, pp. 27:1\u201327:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.27","DOI":"10.4230\/LIPIcs.MFCS.2019.27"},{"key":"18_CR8","doi-asserted-by":"publisher","unstructured":"Bessy, S., Bougeret, M., Thiebaut, J.: Triangle packing in (sparse) tournaments: approximation and kernelization. In: Pruhs, K., Sohler, C. (eds.) 25th Annual European Symposium on Algorithms, ESA 2017, 4\u20136 September 2017, Vienna, Austria. LIPIcs, vol. 87, pp. 14:1\u201314:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.14","DOI":"10.4230\/LIPIcs.ESA.2017.14"},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/978-3-540-77105-0_30","volume-title":"Internet and Network Economics","author":"F Brandt","year":"2007","unstructured":"Brandt, F., Fischer, F.: PageRank as a weak tournament solution. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol. 4858, pp. 300\u2013305. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-77105-0_30"},{"issue":"1","key":"18_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0963548306007887","volume":"16","author":"P Charbit","year":"2007","unstructured":"Charbit, P., Thomass\u00e9, S., Yeo, A.: The minimum feedback arc set problem is NP-hard for tournaments. Comb. Probab. Comput. 16(1), 1\u20134 (2007). https:\/\/doi.org\/10.1017\/S0963548306007887","journal-title":"Comb. Probab. Comput."},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 177\u2013186 (2008)","DOI":"10.1145\/1374376.1374404"},{"key":"18_CR12","doi-asserted-by":"publisher","unstructured":"Davot, T., Isenmann, L., Roy, S., Thiebaut, J.: DegreeWidth: a new parameter for solving problems on tournaments. CoRR abs\/2212.06007 (2022). https:\/\/doi.org\/10.48550\/arXiv.2212.06007","DOI":"10.48550\/arXiv.2212.06007"},{"issue":"3","key":"18_CR13","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(90)90046-3","volume":"41","author":"R Dechter","year":"1990","unstructured":"Dechter, R.: Enhancement schemes for constraint processing: backjumping, learning, and cutset decomposition. Artif. Intell. 41(3), 273\u2013312 (1990). https:\/\/doi.org\/10.1016\/0004-3702(90)90046-3","journal-title":"Artif. Intell."},{"key":"18_CR14","series-title":"Progress in Computer Science and Applied Logic","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Feasible Mathematics II","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized computational feasibility. In: Clote, P., Remmel, J.B. (eds.) Feasible Mathematics II. Progress in Computer Science and Applied Logic, vol. 13, pp. 219\u2013244. Springer, Boston (1995). https:\/\/doi.org\/10.1007\/978-1-4612-2566-9_7"},{"key":"18_CR15","unstructured":"Feige, U.: Faster fast (feedback arc set in tournaments). CoRR abs\/0911.5094 (2009). http:\/\/arxiv.org\/abs\/0911.5094"},{"key":"18_CR16","unstructured":"Fradkin, A.O.: Forbidden structures and algorithms in graphs and digraphs. Ph.D. thesis, USA (2011). aAI3463323"},{"key":"18_CR17","unstructured":"Gavril, F.: Some NP-complete problems on graphs. In: Proceedings of the 11th Conference on Information Sciences and Systems. Johns Hopkins University, Baltimore (1977)"},{"issue":"6","key":"18_CR18","doi-asserted-by":"publisher","first-page":"1358","DOI":"10.1007\/s00224-019-09919-x","volume":"63","author":"F Gurski","year":"2019","unstructured":"Gurski, F., Rehs, C.: Comparing linear width parameters for directed graphs. Theory Comput. Syst. 63(6), 1358\u20131387 (2019). https:\/\/doi.org\/10.1007\/s00224-019-09919-x","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"18_CR19","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0204007","volume":"4","author":"DB Johnson","year":"1975","unstructured":"Johnson, D.B.: Finding all the elementary circuits of a directed graph. SIAM J. Comput. 4(1), 77\u201384 (1975). https:\/\/doi.org\/10.1137\/0204007","journal-title":"SIAM J. Comput."},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-642-17517-6_3","volume-title":"Algorithms and Computation","author":"M Karpinski","year":"2010","unstructured":"Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010. LNCS, vol. 6506, pp. 3\u201314. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-17517-6_3"},{"key":"18_CR21","doi-asserted-by":"publisher","unstructured":"Kenyon-Mathieu, C., Schudy, W.: How to rank with few errors. In: Johnson, D.S., Feige, U. (eds.) Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, 11\u201313 June 2007, pp. 95\u2013103. ACM (2007). https:\/\/doi.org\/10.1145\/1250790.1250806","DOI":"10.1145\/1250790.1250806"},{"key":"18_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-60805-6","volume-title":"Tournament Solutions and Majority Voting","author":"JF Laslier","year":"1997","unstructured":"Laslier, J.F.: Tournament Solutions and Majority Voting, vol. 7. Springer, Heidelberg (1997)"},{"issue":"6","key":"18_CR23","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T Leighton","year":"1999","unstructured":"Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM (JACM) 46(6), 787\u2013832 (1999)","journal-title":"J. ACM (JACM)"},{"key":"18_CR24","unstructured":"Thiebaut, J.: Algorithmic and structural results on directed cycles in dense digraphs. (R\u00e9sultats algorithmiques et structurels sur les cycles orient\u00e9s dans les digraphes denses). Ph.D. thesis, University of Montpellier, France (2019). https:\/\/tel.archives-ouvertes.fr\/tel-02491420"},{"issue":"3","key":"18_CR25","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1287\/moor.1090.0385","volume":"34","author":"A van Zuylen","year":"2009","unstructured":"van Zuylen, A., Williamson, D.P.: Deterministic pivoting algorithms for constrained ranking and clustering problems. Math. Oper. Res. 34(3), 594\u2013620 (2009). https:\/\/doi.org\/10.1287\/moor.1090.0385","journal-title":"Math. Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43380-1_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T20:30:59Z","timestamp":1695414659000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43380-1_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031433795","9783031433801"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43380-1_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"23 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Fribourg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Switzerland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"49","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.unifr.ch\/wg2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}