{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,7,25]],"date-time":"2023-07-25T05:29:40Z","timestamp":1690262980373},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,2,23]],"date-time":"2013-02-23T00:00:00Z","timestamp":1361577600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,11]]},"DOI":"10.1007\/s00224-013-9453-4","type":"journal-article","created":{"date-parts":[[2013,2,22]],"date-time":"2013-02-22T11:57:39Z","timestamp":1361534259000},"page":"609-620","source":"Crossref","is-referenced-by-count":4,"title":["A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments"],"prefix":"10.1007","volume":"53","author":[{"given":"Pranabendu","family":"Misra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,2,23]]},"reference":[{"issue":"7","key":"9453_CR1","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","volume":"76","author":"F.N. Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: A kernelization algorithm for d-hitting set. J. Comput. Syst. Sci. 76(7), 524\u2013531 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"9453_CR2","doi-asserted-by":"crossref","first-page":"684","DOI":"10.1145\/1060590.1060692","volume-title":"STOC","author":"N. Ailon","year":"2005","unstructured":"Ailon,\u00a0N., Charikar,\u00a0M., Newman,\u00a0A.: Aggregating inconsistent information: ranking and clustering. In: STOC, pp. 684\u2013693 (2005)"},{"issue":"1","key":"9453_CR3","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1137\/050623905","volume":"20","author":"N. Alon","year":"2006","unstructured":"Alon,\u00a0N.: Ranking tournaments. SIAM J. Discrete Math. 20(1), 137\u2013142 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"9453_CR4","series-title":"LNCS","first-page":"49","volume-title":"ICALP","author":"N. Alon","year":"2009","unstructured":"Alon,\u00a0N., Lokshtanov,\u00a0D., Saurabh,\u00a0S.: Fast FAST. In: ICALP. LNCS, vol. 5555, pp. 49\u201358 (2009)"},{"key":"9453_CR5","series-title":"Algorithms and Applications. Springer Monographs in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84800-998-1","volume-title":"Digraphs: Theory","author":"J. Bang-Jensen","year":"2009","unstructured":"Bang-Jensen,\u00a0J., Gutin,\u00a0G.: Digraphs: Theory. Algorithms and Applications. Springer Monographs in Mathematics. Springer, Berlin (2009)"},{"issue":"3","key":"9453_CR6","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1137\/0405027","volume":"5","author":"J. Bang-Jensen","year":"1992","unstructured":"Bang-Jensen,\u00a0J., Thomassen,\u00a0C.: A polynomial algorithm for the 2-path problem for semicomplete digraphs. SIAM J. Discrete Math. 5(3), 366\u2013376 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"9453_CR7","first-page":"37","volume-title":"FSTTCS","author":"S. Bessy","year":"2009","unstructured":"Bessy,\u00a0S., Fomin, F.V., Gaspers,\u00a0S., Paul,\u00a0C., Perez,\u00a0A., Saurabh,\u00a0S., Thomass\u00e9,\u00a0S.: Kernels for feedback arc set in tournaments. In: FSTTCS, pp. 37\u201347 (2009)"},{"issue":"8","key":"9453_CR8","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin,\u00a0D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9453_CR9","first-page":"629","volume-title":"FOCS","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov,\u00a0D., Penninkx,\u00a0E., Saurabh,\u00a0S., Thilikos, D.M.: (Meta) Kernelization. In: FOCS, pp. 629\u2013638 (2009)"},{"issue":"2","key":"9453_CR10","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1287\/moor.27.2.361.328","volume":"27","author":"M.C. Cai","year":"2002","unstructured":"Cai, M.C., Deng,\u00a0X., Zang,\u00a0W.: A min-max theorem on feedback vertex sets. Math. Oper. Res. 27(2), 361\u2013371 (2002)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"9453_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0963548306007887","volume":"16","author":"P. Charbit","year":"2007","unstructured":"Charbit,\u00a0P., Thomass\u00e9,\u00a0S., Yeo,\u00a0A.: The minimum feedback arc set problem is NP-hard for tournaments. Comb. Probab. Comput. 16(1), 1\u20134 (2007)","journal-title":"Comb. Probab. Comput."},{"key":"9453_CR12","first-page":"451","volume-title":"NIPS","author":"W.W. Cohen","year":"1997","unstructured":"Cohen, W.W., Schapire, R.E., Singer,\u00a0Y.: Learning to order things. In: NIPS, pp. 451\u2013457 (1997)"},{"key":"9453_CR13","first-page":"251","volume-title":"STOC","author":"H. Dell","year":"2010","unstructured":"Dell,\u00a0H., van Melkebeek,\u00a0D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: STOC, pp. 251\u2013260 (2010)"},{"issue":"1","key":"9453_CR14","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/j.jda.2009.08.001","volume":"8","author":"M. Dom","year":"2010","unstructured":"Dom,\u00a0M., Guo,\u00a0J., H\u00fcffner,\u00a0F., Niedermeier,\u00a0R., Tru\u00df,\u00a0A.: Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms 8(1), 76\u201386 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"9453_CR15","series-title":"LNCS","first-page":"378","volume-title":"ICALP","author":"M. Dom","year":"2009","unstructured":"Dom,\u00a0M., Lokshtanov,\u00a0D., Saurabh,\u00a0S.: Incompressibility through colors and IDs. In: ICALP. LNCS, vol. 5555, pp. 378\u2013389 (2009)"},{"key":"9453_CR16","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1145\/371920.372165","volume-title":"WWW","author":"C. Dwork","year":"2001","unstructured":"Dwork,\u00a0C., Kumar,\u00a0R., Naor,\u00a0M., Sivakumar,\u00a0D.: Rank aggregation methods for the web. In: WWW, pp. 613\u2013622 (2001)"},{"key":"9453_CR17","first-page":"503","volume-title":"SODA","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Lokshtanov,\u00a0D., Saurabh,\u00a0S., Thilikos, D.M.: Bidimensionality and kernels. In: SODA, pp. 503\u2013510 (2010)"},{"issue":"8\u201310","key":"9453_CR18","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1016\/j.tcs.2008.10.021","volume":"410","author":"J. Guo","year":"2009","unstructured":"Guo,\u00a0J.: A more effective linear kernelization for cluster editing. Theor. Comput. Sci. 410(8\u201310), 718\u2013726 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2\u20133","key":"9453_CR19","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.ipl.2006.11.016","volume":"102","author":"J. Guo","year":"2007","unstructured":"Guo,\u00a0J., H\u00fcffner,\u00a0F., Moser,\u00a0H.: Feedback arc set in bipartite tournaments is np-complete. Inf. Process. Lett. 102(2\u20133), 62\u201365 (2007)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9453_CR20","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/j.ipl.2007.08.023","volume":"105","author":"S. Gupta","year":"2008","unstructured":"Gupta,\u00a0S.: Feedback arc set problem in bipartite tournaments. Inf. Process. Lett. 105(4), 150\u2013154 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9453_CR21","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.cosrev.2010.01.001","volume":"4","author":"M. Habib","year":"2010","unstructured":"Habib,\u00a0M., Paul,\u00a0C.: A survey of the algorithmic aspects of modular decomposition. Comput. Sci. Rev. 4(1), 41\u201359 (2010)","journal-title":"Comput. Sci. Rev."},{"key":"9453_CR22","doi-asserted-by":"crossref","unstructured":"Karpinski,\u00a0M., Schudy,\u00a0W.: Faster algorithms for feedback arc set tournament, kemeny rank aggregation and betweenness tournament. CoRR abs\/1006.4396 (2010)","DOI":"10.1007\/978-3-642-17517-6_3"},{"key":"9453_CR23","first-page":"571","volume":"88","author":"J. Kemeny","year":"1959","unstructured":"Kemeny,\u00a0J.: Mathematics without numbers. Daedalus 88, 571\u2013591 (1959)","journal-title":"Daedalus"},{"key":"9453_CR24","volume-title":"Mathematical Models in the Social Sciences","author":"J. Kemeny","year":"1962","unstructured":"Kemeny,\u00a0J., Snell,\u00a0J.: Mathematical Models in the Social Sciences. Blaisdell, Boston (1962)"},{"key":"9453_CR25","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1145\/1250790.1250806","volume-title":"STOC","author":"C. Kenyon-Mathieu","year":"2007","unstructured":"Kenyon-Mathieu,\u00a0C., Schudy,\u00a0W.: How to rank with few errors. In: STOC, pp. 95\u2013103 (2007)"},{"key":"9453_CR26","first-page":"333","volume-title":"ISAAC","author":"P. Misra","year":"2011","unstructured":"Misra,\u00a0P., Raman,\u00a0V., Ramanujan, M.S., Saurabh,\u00a0S.: A polynomial kernel for feedback arc set on bipartite tournaments. In: ISAAC, pp. 333\u2013343 (2011)"},{"issue":"3","key":"9453_CR27","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1016\/j.tcs.2005.10.010","volume":"351","author":"V. Raman","year":"2006","unstructured":"Raman,\u00a0V., Saurabh,\u00a0S.: Parameterized algorithms for feedback set problems and their duals in tournaments. Theor. Comput. Sci. 351(3), 446\u2013458 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9453_CR28","series-title":"LNCS","first-page":"999","volume-title":"OTM Conferences (2)","author":"B. Sanghvi","year":"2010","unstructured":"Sanghvi,\u00a0B., Koul,\u00a0N., Honavar,\u00a0V.: Identifying and eliminating inconsistencies in mappings across hierarchical ontologies. In: OTM Conferences (2). LNCS, vol. 6427, pp. 999\u20131008 (2010)"},{"key":"9453_CR29","series-title":"LNCS","first-page":"218","volume-title":"WG","author":"E. Speckenmeyer","year":"1989","unstructured":"Speckenmeyer,\u00a0E.: On feedback problems in digraphs. In: WG. LNCS, vol. 411, pp. 218\u2013231 (1989)"},{"key":"9453_CR30","series-title":"LNCS","first-page":"634","volume-title":"ICALP","author":"M. Tedder","year":"2008","unstructured":"Tedder,\u00a0M., Corneil, D.G., Habib,\u00a0M., Paul,\u00a0C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: ICALP. LNCS, pp. 634\u2013645 (2008)"},{"key":"9453_CR31","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9,\u00a0S.: A 4k 2 kernel for feedback vertex set. ACM Trans. Algorithms 6(2) (2010)","DOI":"10.1145\/1721837.1721848"},{"key":"9453_CR32","series-title":"LNCS","first-page":"825","volume-title":"MFCS","author":"M. Xiao","year":"2012","unstructured":"Xiao,\u00a0M., Guo,\u00a0J.: A quadratic vertex kernel for feedback arc set in bipartite tournaments. In: MFCS. LNCS, vol. 7464, pp. 825\u2013835 (2012)"},{"issue":"23","key":"9453_CR33","doi-asserted-by":"crossref","first-page":"2556","DOI":"10.1016\/j.tcs.2010.10.047","volume":"412","author":"A. Zuylen van","year":"2011","unstructured":"van Zuylen,\u00a0A.: Linear programming based approximation algorithms for feedback set problems in bipartite tournaments. Theor. Comput. Sci. 412(23), 2556\u20132561 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9453_CR34","first-page":"405","volume-title":"SODA","author":"A. Zuylen van","year":"2007","unstructured":"van Zuylen,\u00a0A., Hegde,\u00a0R., Jain,\u00a0K., Williamson, D.P.: Deterministic pivoting algorithms for constrained ranking and clustering problems. In: SODA, pp. 405\u2013414 (2007)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9453-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9453-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9453-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,29]],"date-time":"2023-06-29T18:31:04Z","timestamp":1688063464000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9453-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,23]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["9453"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9453-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2,23]]}}}