{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:25:11Z","timestamp":1725600311170},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229923"},{"type":"electronic","value":"9783642229930"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22993-0_45","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T12:44:46Z","timestamp":1312893886000},"page":"497-507","source":"Crossref","is-referenced-by-count":7,"title":["Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem"],"prefix":"10.1007","author":[{"given":"Christophe","family":"Paul","sequence":"first","affiliation":[]},{"given":"Anthony","family":"Perez","sequence":"additional","affiliation":[]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"45_CR1","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"A. Aho","year":"1981","unstructured":"Aho, A., Sagiv, Y., Szymansk, T., Ullman, J.: Inferring a tree from lowest common ancestor with an application to the optimization of relational expressions. SIAM Journal on Computing\u00a010(3), 405\u2013421 (1981)","journal-title":"SIAM Journal on Computing"},{"issue":"8","key":"45_CR2","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1016\/j.ic.2007.02.006","volume":"205","author":"N. Ailon","year":"2007","unstructured":"Ailon, N., Alon, N.: Hardness of fully dense problems. Inf. Comput.\u00a0205(8), 1117\u20131129 (2007)","journal-title":"Inf. Comput."},{"issue":"1","key":"45_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":"45_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)"},{"key":"45_CR5","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-8858(86)90038-2","volume":"7","author":"H.-J. Bandelt","year":"1986","unstructured":"Bandelt, H.-J., Dress, A.: Reconstructing the shape of a tree from observed dissimilarity data. Advances in Applied Mathematics\u00a07, 309\u2013343 (1986)","journal-title":"Advances in Applied Mathematics"},{"key":"45_CR6","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 2009. LIPIcs, vol.\u00a04, pp. 37\u201347 (2009)"},{"key":"45_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-11269-0_2","volume-title":"Parameterized and Exact Computation","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L.: Kernelization: New upper and lower bound techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 17\u201337. Springer, Heidelberg (2009)"},{"key":"45_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J.A. Bondy","year":"1976","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. North-Holland, Amsterdam (1976)"},{"key":"45_CR9","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.endm.2009.02.008","volume":"32","author":"D. Br\u00fcgmann","year":"2009","unstructured":"Br\u00fcgmann, D., Komusiewicz, C., Moser, H.: On generating triangle-free graphs. Electronic Notes in Discrete Mathematics\u00a032, 51\u201358 (2009)","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"11","key":"45_CR10","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1016\/j.dam.2010.03.004","volume":"158","author":"J. Byrka","year":"2010","unstructured":"Byrka, J., Guillemot, S., Jansson, J.: New results on optimizing rooted triplets consistency. Discrete Applied Mathematics\u00a0158(11), 1136\u20131147 (2010)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"45_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."},{"key":"45_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/11758471_31","volume-title":"Algorithms and Complexity","author":"M. Dom","year":"2006","unstructured":"Dom, M., Guo, J., H\u00fcffner, F., Niedermeier, R., Tru\u00df, A.: Fixed-parameter tractability results for feedback set problems in tournaments. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol.\u00a03998, pp. 320\u2013331. Springer, Heidelberg (2006)"},{"key":"45_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"45_CR14","doi-asserted-by":"publisher","first-page":"269","DOI":"10.4153\/CMB-1965-017-1","volume":"8","author":"P. Erd\u00f6s","year":"1965","unstructured":"Erd\u00f6s, P., Moon, J.W.: On sets on consistent arcs in tournaments. Canad. Math. Bull.\u00a08, 269\u2013271 (1965)","journal-title":"Canad. Math. Bull."},{"key":"45_CR15","doi-asserted-by":"crossref","unstructured":"Guillemot, S., Berry, V.: Fixed-parameter tractability of the maximum agreement supertree problem. IEEE\/ACM Trans. Comput. Biology Bioinform.\u00a07(2) (2010)","DOI":"10.1109\/TCBB.2010.30"},{"key":"45_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-642-13562-0_23","volume-title":"Theory and Applications of Models of Computation","author":"S. Guillemot","year":"2010","unstructured":"Guillemot, S., Mnich, M.: Kernel and fast algorithm for dense triplet inconsistency. In: Kratochv\u00edl, J., Li, A., Fiala, J., Kolman, P. (eds.) TAMC 2010. LNCS, vol.\u00a06108, pp. 247\u2013257. Springer, Heidelberg (2010)"},{"issue":"37","key":"45_CR17","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","volume":"10","author":"P. Hall","year":"1935","unstructured":"Hall, P.: On representatives of subsets. J. London Math. Soc.\u00a010(37), 26\u201330 (1935)","journal-title":"J. London Math. Soc."},{"key":"45_CR18","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.\u00a06506, pp. 3\u201314. Springer, Heidelberg (2010)"},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"Kenyon-Mathieu, C., Schudy, W.: How to rank with few errors. In: STOC 2007, pp. 95\u2013103 (2007)","DOI":"10.1145\/1250790.1250806"},{"issue":"3","key":"45_CR20","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":"45_CR21","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/S0021-9800(70)80061-8","volume":"9","author":"K.D. Reid","year":"1970","unstructured":"Reid, K.D., Parker, E.T.: Disproof of a conjecture of Erd\u00f6s and Moser on tournaments. J. Combin. Theory\u00a09, 225\u2013238 (1970)","journal-title":"J. Combin. Theory"},{"key":"45_CR22","unstructured":"Saurabh, S.: Chromatic coding and universal (hyper-)graph coloring families. Parameterized Complexity News, 49\u201358 (June 2009)"},{"key":"45_CR23","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C. Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford Lecture Series in Mathematics and Its Applications, vol.\u00a024. Oxford University Press, Oxford (2003)"},{"issue":"5","key":"45_CR24","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/j.ipl.2009.12.002","volume":"110","author":"J. Wang","year":"2010","unstructured":"Wang, J., Ning, D., Feng, Q., Chen, J.: An improved kernelization for P2-packing. Inf. Process. Lett.\u00a0110(5), 188\u2013192 (2010)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22993-0_45.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T20:13:51Z","timestamp":1712693631000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22993-0_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229923","9783642229930"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22993-0_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}