{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T21:18:15Z","timestamp":1718745495886},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s00453-020-00788-2","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T16:04:15Z","timestamp":1609776255000},"page":"1393-1420","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Packing Arc-Disjoint Cycles in Tournaments"],"prefix":"10.1007","volume":"83","author":[{"given":"St\u00e9phane","family":"Bessy","sequence":"first","affiliation":[]},{"given":"Marin","family":"Bougeret","sequence":"additional","affiliation":[]},{"given":"R.","family":"Krithika","sequence":"additional","affiliation":[]},{"given":"Abhishek","family":"Sahu","sequence":"additional","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]},{"given":"Jocelyn","family":"Thiebaut","sequence":"additional","affiliation":[]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"issue":"16","key":"788_CR1","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1016\/j.ipl.2010.04.020","volume":"110","author":"FN Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: An improved Kernelization algorithm for r-set packing. Inf. Process. Lett. 110(16), 621\u2013624 (2010)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"788_CR2","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.disc.2014.09.010","volume":"338","author":"I Akaria","year":"2015","unstructured":"Akaria, I., Yuster, R.: Packing edge-disjoint triangles in regular and almost regular tournaments. Discrete Math. 338(2), 217\u2013228 (2015)","journal-title":"Discrete Math."},{"issue":"1","key":"788_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. Discrete Math. 20(1), 137\u2013142 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"788_CR4","doi-asserted-by":"crossref","unstructured":"Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: 36th International Colloquium on Automata, Languages, and Programming (ICALP 2009) Part I, pp. 49\u201358 (2009)","DOI":"10.1007\/978-3-642-02927-1_6"},{"issue":"4","key":"788_CR5","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"788_CR6","first-page":"131","volume":"115","author":"J Bang-Jensen","year":"1996","unstructured":"Bang-Jensen, J., Gutin, G.: Paths, trees and cycles in tournaments. Congressus Numerantium 115, 131\u2013170 (1996)","journal-title":"Congressus Numerantium"},{"key":"788_CR7","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.: Digraphs: Theory, Algorithms and Applications. Springer, London (2009)"},{"key":"788_CR8","unstructured":"Bessy, S., Bougeret, M., Thiebaut, J.: Triangle packing in (sparse) tournaments: approximation and kernelization. In: 25th Annual European Symposium on Algorithms (ESA 2017), vol. 87, pp. 14:1\u201314:13 (2017)"},{"key":"788_CR9","unstructured":"Bessy, S., Bougeret, M., Thiebaut, J.: (Arc-disjoint) cycle packing in tournament: classical and parameterized complexity (2018). arXiv:1802.06669"},{"issue":"6","key":"788_CR10","doi-asserted-by":"publisher","first-page":"1071","DOI":"10.1016\/j.jcss.2010.10.001","volume":"77","author":"S Bessy","year":"2011","unstructured":"Bessy, S., Fomin, F.V., Gaspers, S., Paul, C., Perez, A., Saurabh, S., Thomass\u00e9, S.: Kernels for feedback arc set in tournaments. J. Comput. Syst. Sci. 77(6), 1071\u20131078 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"788_CR11","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/S0129054194000049","volume":"5","author":"HL Bodlaender","year":"1994","unstructured":"Bodlaender, H.L.: On disjoint cycles. Int. J. Found. Comput. Sci. 5(1), 59\u201368 (1994)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"35","key":"788_CR12","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"788_CR13","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0196-6774(03)00052-X","volume":"48","author":"A Caprara","year":"2003","unstructured":"Caprara, A., Panconesi, A., Rizzi, R.: Packing cycles in undirected graphs. J. Algorithms 48(1), 239\u2013256 (2003)","journal-title":"J. Algorithms"},{"issue":"1","key":"788_CR14","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)","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"788_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00493-008-2331-z","volume":"28","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky, M., Seymour, P., Sullivan, B.: Cycles in dense digraphs. Combinatorica 28(1), 1\u201318 (2008)","journal-title":"Combinatorica"},{"key":"788_CR16","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1613\/jair.587","volume":"10","author":"WW Cohen","year":"1999","unstructured":"Cohen, W.W., Schapire, R.E., Singer, Y.: Learning to order things. J. Artif. Intell. Res. 10, 243\u2013270 (1999)","journal-title":"J. Artif. Intell. Res."},{"key":"788_CR17","unstructured":"Conitzer, V.: Computing slater rankings using similarities among candidates. In: 21st National Conference on Artificial Intelligence, vol. 1, pp. 613\u2013619 (2006)"},{"key":"788_CR18","doi-asserted-by":"crossref","unstructured":"Cygan, M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pp. 509\u2013518 (2013)","DOI":"10.1109\/FOCS.2013.61"},{"key":"788_CR19","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)"},{"key":"788_CR20","unstructured":"de Borda, J.-C.: M\u00e9moire sur les \u00e9lections au scrutin. Histoire de l\u2019Acad\u00e9mie Royale des Sciences (1781)"},{"issue":"2","key":"788_CR21","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0166-218X(92)00171-H","volume":"50","author":"D Dorninger","year":"1994","unstructured":"Dorninger, D.: Hamiltonian circuits determining the order of chromosomes. Discrete Appl. Math. 50(2), 159\u2013168 (1994)","journal-title":"Discrete Appl. Math."},{"key":"788_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, London (2013)"},{"key":"788_CR23","doi-asserted-by":"crossref","unstructured":"Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: 10th International World Wide Web Conference, pp. 613\u2013622 (2001)","DOI":"10.1145\/371920.372165"},{"key":"788_CR24","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1965-035-8","volume":"17","author":"P Erd\u0151s","year":"1965","unstructured":"Erd\u0151s, P., P\u00f3sa, L.: On independent circuits contained in a graph. Can. J. Math. 17, 347\u2013352 (1965)","journal-title":"Can. J. Math."},{"issue":"4","key":"788_CR25","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S Even","year":"1976","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 5(4), 691\u2013703 (1976)","journal-title":"SIAM J. Comput."},{"key":"788_CR26","unstructured":"Feige, U.: Faster FAST(Feedback Arc Set in Tournaments) (2009). arXiv:0911.5094"},{"key":"788_CR27","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"788_CR28","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Fast local search algorithm for weighted feedback arc set in tournaments. In: 24th AAAI Conference on Artificial Intelligence, pp. 65\u201370 (2010)","DOI":"10.1609\/aaai.v24i1.7557"},{"key":"788_CR29","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)"},{"issue":"2","key":"788_CR30","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10(2), 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"788_CR31","unstructured":"Gardner, R.B.: Optimal packings and coverings of the complete directed graph with $$3$$-circuits and with transitive triples. In: 28th Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 127, pp. 161\u2013170 (1997)"},{"key":"788_CR32","doi-asserted-by":"crossref","unstructured":"Grohe, M., Gr\u00fcber, M.: Parameterized approximability of the disjoint cycle problem. In: 34th International Colloquium on Automata. Languages, and Programming (ICALP), pp. 363\u2013374. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-73420-8_33"},{"issue":"4","key":"788_CR33","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."},{"key":"788_CR34","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. In: 21st International Symposium on Algorithms and Computation (ISAAC 2010), pp. 3\u201314 (2010)","DOI":"10.1007\/978-3-642-17517-6_3"},{"key":"788_CR35","first-page":"191","volume":"2","author":"TP Kirkman","year":"1847","unstructured":"Kirkman, T.P.: On a problem in combinations. Camb. Dublin Math. J. 2, 191\u2013204 (1847)","journal-title":"Camb. Dublin Math. J."},{"key":"788_CR36","unstructured":"Krithika, R., Sahu, A., Saurabh, S., Zehavi, M.: The parameterized complexity of packing arc-disjoint cycles in tournaments (2018). arXiv:1802.07090"},{"issue":"4","key":"788_CR37","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1145\/1290672.1290685","volume":"3","author":"M Krivelevich","year":"2007","unstructured":"Krivelevich, M., Nutov, Z., Salavatipour, M.R., Yuster, J.V., Yuster, R.: Approximation algorithms and hardness results for cycle packing problems. ACM Trans. Algorithms 3(4), 48 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"788_CR38","unstructured":"Krivelevich, M., Nutov, Z., Yuster, R.: Approximation algorithms for cycle packing problems. In: 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 556\u2013561 (2005)"},{"key":"788_CR39","doi-asserted-by":"crossref","unstructured":"Le, T., Lokshtanov, D., Saurabh, S., Thomass\u00e9, S., Zehavi, M.: Subquadratic kernels for implicit 3-hitting set and 3-set packing problems. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 331\u2013342 (2018)","DOI":"10.1137\/1.9781611975031.23"},{"key":"788_CR40","unstructured":"le Marquis de Condorcet, M.: Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix. Imprimerie Royale, Paris (1785)"},{"key":"788_CR41","unstructured":"Lokshtanov, D., Mouawad, A., Saurabh, S., Zehavi, M.: Packing cycles faster than Erd\u0151s\u2013P\u00f3sa. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pp. 71:1\u201371:15 (2017)"},{"issue":"2","key":"788_CR42","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1112\/jlms\/s2-17.3.369","volume":"17","author":"CL Lucchesi","year":"1978","unstructured":"Lucchesi, C.L., Younger, D.H.: A minimax theorem for directed graphs. J. Lond. Math. Soc. 17(2), 369\u2013374 (1978)","journal-title":"J. Lond. Math. Soc."},{"issue":"2","key":"788_CR43","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"key":"788_CR44","volume-title":"Topics on Tournaments","author":"JW Moon","year":"1968","unstructured":"Moon, J.W.: Topics on Tournaments. Holt, Rinehart and Winston, New York (1968)"},{"key":"788_CR45","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"2003","unstructured":"Papadimitriou, C.H.: Computational Complexity. Wiley, New York (2003)"},{"key":"788_CR46","unstructured":"Pilipczuk, M.: Tournaments and optimality: new results in parameterized complexity. PhD thesis, The University of Bergen (2013)"},{"issue":"3","key":"788_CR47","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1016\/j.tcs.2005.10.010","volume":"351","author":"V Raman","year":"2006","unstructured":"Raman, V., Saurabh, S.: Parameterized algorithms for feedback set problems and their duals in tournaments. Theor. Comput. Sci. 351(3), 446\u2013458 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"788_CR48","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1137\/0219054","volume":"19","author":"JP Schmidt","year":"1990","unstructured":"Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput. 19(5), 775\u2013786 (1990)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"788_CR49","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/070697781","volume":"24","author":"A Slivkins","year":"2010","unstructured":"Slivkins, A.: Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM J. Discrete Math. 24(1), 146\u2013157 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"788_CR50","doi-asserted-by":"crossref","unstructured":"Speckenmeyer, E.: On feedback problems in digraphs. In: 15th International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 218\u2013231 (1990)","DOI":"10.1007\/3-540-52292-1_16"},{"issue":"1","key":"788_CR51","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"CA Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified NP-complete satisfiability problem. Discrete Appl. Math. 8(1), 85\u201389 (1984)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"788_CR52","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1002\/jgt.21691","volume":"74","author":"R Yuster","year":"2013","unstructured":"Yuster, R.: Packing triangles in regular tournaments. J. Graph Theory 74(1), 58\u201366 (2013)","journal-title":"J. Graph Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00788-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00788-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00788-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,10]],"date-time":"2022-12-10T12:09:27Z","timestamp":1670674167000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00788-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":52,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["788"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00788-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"10 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}