{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T15:56:48Z","timestamp":1725638208087},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642255908"},{"type":"electronic","value":"9783642255915"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-25591-5_35","type":"book-chapter","created":{"date-parts":[[2011,12,3]],"date-time":"2011-12-03T00:32:34Z","timestamp":1322872354000},"page":"333-343","source":"Crossref","is-referenced-by-count":1,"title":["A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments"],"prefix":"10.1007","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","reference":[{"issue":"7","key":"35_CR1","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a076(7), 524\u2013531 (2010)","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. In: ACM Symposium on Theory of Computing (STOC), pp. 684\u2013693 (2005)","key":"35_CR2","DOI":"10.1145\/1060590.1060692"},{"issue":"1","key":"35_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.\u00a020(1), 137\u2013142 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"35_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-642-02927-1_6","volume-title":"Automata, Languages and Programming","author":"N. Alon","year":"2009","unstructured":"Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 49\u201358. Springer, Heidelberg (2009)"},{"issue":"3","key":"35_CR5","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1137\/0405027","volume":"5","author":"J. Bang-Jensen","year":"1992","unstructured":"Bang-Jensen, J., Thomassen, C.: A polynomial algorithm for the 2-path problem for semicomplete digraphs. SIAM J. Discrete Math.\u00a05(3), 366\u2013376 (1992)","journal-title":"SIAM J. Discrete Math."},{"unstructured":"Bessy, S., Fomin, F.V., Gaspers, S., Paul, C., Perez, A., Saurabh, S., Thomass\u00e9, S.: Kernels for feedback arc set in tournaments. In: FSTTCS, pp. 37\u201347 (2009)","key":"35_CR6"},{"issue":"8","key":"35_CR7","doi-asserted-by":"publisher","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, D.: On problems without polynomial kernels. J. Comput. Syst. Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. In: FOCS, pp. 629\u2013638 (2009)","key":"35_CR8","DOI":"10.1109\/FOCS.2009.46"},{"unstructured":"Borda, J.: M\u00e9moire sur les \u00e9lections au scrutin. Histoire de l\u2019Acad\u00e9mie Royale des Sciences (1781)","key":"35_CR9"},{"issue":"2","key":"35_CR10","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1287\/moor.27.2.361.328","volume":"27","author":"M. Cheng Cai","year":"2002","unstructured":"Cheng Cai, M., Deng, X., Zang, W.: A min-max theorem on feedback vertex sets. Math. Oper. Res.\u00a027(2), 361\u2013371 (2002)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"35_CR11","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. Combin. Probab. Comput.\u00a016(1), 1\u20134 (2007)","journal-title":"Combin. Probab. Comput."},{"unstructured":"Cohen, W.W., Schapire, R.E., Singer, Y.: Learning to order things. In: Advances in Neural Information Processing Systems (NIPS), pp. 451\u2013457 (1997)","key":"35_CR12"},{"unstructured":"Condorcet, M.: Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix (1785)","key":"35_CR13"},{"doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: STOC, pp. 251\u2013260. ACM (2010)","key":"35_CR14","DOI":"10.1145\/1806689.1806725"},{"key":"35_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"Automata, Languages and Programming","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through Colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 378\u2013389. Springer, Heidelberg (2009)"},{"issue":"1","key":"35_CR16","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jda.2009.08.001","volume":"8","author":"M. Dom","year":"2010","unstructured":"Dom, M., Guo, J., H\u00fcffner, F., Niedermeier, R., Tru\u00df, A.: Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms\u00a08(1), 76\u201386 (2010)","journal-title":"J. Discrete Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: World Wide Web Conference, WWW (2001)","key":"35_CR17","DOI":"10.1145\/371920.372165"},{"doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: SODA, pp. 503\u2013510 (2010)","key":"35_CR18","DOI":"10.1137\/1.9781611973075.43"},{"issue":"8-10","key":"35_CR19","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/j.tcs.2008.10.021","volume":"410","author":"J. Guo","year":"2009","unstructured":"Guo, J.: A more effective linear kernelization for cluster editing. Theor. Comput. Sci.\u00a0410(8-10), 718\u2013726 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2-3","key":"35_CR20","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.ipl.2006.11.016","volume":"102","author":"J. Guo","year":"2007","unstructured":"Guo, J., H\u00fcffner, F., Moser, H.: Feedback arc set in bipartite tournaments is NP-Complete. Inf. Process. Lett.\u00a0102(2-3), 62\u201365 (2007)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"35_CR21","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.ipl.2007.08.023","volume":"105","author":"S. Gupta","year":"2008","unstructured":"Gupta, S.: Feedback arc set problem in bipartite tournaments. Inf. Process. Lett.\u00a0105(4), 150\u2013154 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"35_CR22","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.cosrev.2010.01.001","volume":"4","author":"M. Habib","year":"2010","unstructured":"Habib, M., Paul, C.: A survey of the algorithmic aspects of modular decomposition. Computer Science Review\u00a04(1), 41\u201359 (2010)","journal-title":"Computer Science Review"},{"doi-asserted-by":"crossref","unstructured":"Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set tournament, kemeny rank aggregation and betweenness tournament. CoRR abs\/1006.4396 (2010)","key":"35_CR23","DOI":"10.1007\/978-3-642-17517-6_3"},{"key":"35_CR24","first-page":"571","volume":"88","author":"J. Kemeny","year":"1959","unstructured":"Kemeny, J.: Mathematics without numbers. Daedalus\u00a088, 571\u2013591 (1959)","journal-title":"Daedalus"},{"unstructured":"Kemeny, J., Snell, J.: Mathematical models in the social sciences. Blaisdell (1962)","key":"35_CR25"},{"doi-asserted-by":"crossref","unstructured":"Kenyon-Mathieu, C., Schudy, W.: How to rank with few errors. In: ACM Symposium on Theory of Computing (STOC), pp. 95\u2013103 (2007)","key":"35_CR26","DOI":"10.1145\/1250790.1250806"},{"issue":"3","key":"35_CR27","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.\u00a0351(3), 446\u2013458 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"35_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1007\/978-3-642-16949-6_24","volume-title":"On the Move to Meaningful Internet Systems, OTM 2010","author":"B. Sanghvi","year":"2010","unstructured":"Sanghvi, B., Koul, N., Honavar, V.: Identifying and Eliminating Inconsistencies in Mappings Across Hierarchical Ontologies. In: Meersman, R., Dillon, T., Herrero, P. (eds.) OTM 2010. LNCS, vol.\u00a06427, pp. 999\u20131008. Springer, Heidelberg (2010)"},{"key":"35_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/3-540-52292-1_16","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"E. Speckenmeyer","year":"1990","unstructured":"Speckenmeyer, E.: On Feedback Problems in Digraphs. In: Nagl, M. (ed.) WG 1989. LNCS, vol.\u00a0411, pp. 218\u2013231. Springer, Heidelberg (1990)"},{"key":"35_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1007\/978-3-540-70575-8_52","volume-title":"Automata, Languages and Programming","author":"M. Tedder","year":"2008","unstructured":"Tedder, M., Corneil, D.G., Habib, M., Paul, C.: Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 634\u2013645. Springer, Heidelberg (2008)"},{"doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A 4k 2 kernel for feedback vertex set. ACM Transactions on Algorithms\u00a06(2) (2010)","key":"35_CR31","DOI":"10.1145\/1721837.1721848"},{"unstructured":"van Zuylen, A., Hegde, R., Jain, K., Williamson, D.P.: Deterministic pivoting algorithms for constrained ranking and clustering problems. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 405\u2013414 (2007)","key":"35_CR32"},{"issue":"23","key":"35_CR33","doi-asserted-by":"publisher","first-page":"2556","DOI":"10.1016\/j.tcs.2010.10.047","volume":"412","author":"A. Zuylen van","year":"2011","unstructured":"van Zuylen, A.: Linear programming based approximation algorithms for feedback set problems in bipartite tournaments. Theor. Comput. Sci.\u00a0412(23), 2556\u20132561 (2011)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-25591-5_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T06:11:25Z","timestamp":1561011085000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25591-5_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642255908","9783642255915"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25591-5_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}