{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T20:07:09Z","timestamp":1709669229116},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T00:00:00Z","timestamp":1561075200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T00:00:00Z","timestamp":1561075200000},"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":[[2019,9]]},"DOI":"10.1007\/s00453-019-00599-0","type":"journal-article","created":{"date-parts":[[2019,6,21]],"date-time":"2019-06-21T11:02:35Z","timestamp":1561114955000},"page":"3803-3841","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Parameterized Complexity of Cycle Packing: Indifference is Not an Issue"],"prefix":"10.1007","volume":"81","author":[{"given":"R.","family":"Krithika","sequence":"first","affiliation":[]},{"given":"Abhishek","family":"Sahu","sequence":"additional","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,21]]},"reference":[{"issue":"4","key":"599_CR1","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"},{"issue":"1","key":"599_CR2","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":"2","key":"599_CR3","first-page":"263","volume":"63","author":"HL Bodlaender","year":"2013","unstructured":"Bodlaender, H.L., Jansen, B.M.P.: Vertex cover kernelization revisited: upper and lower bounds for a refined parameter. Theory Comput. Syst. 63(2), 263\u2013299 (2013)","journal-title":"Theory Comput. Syst."},{"key":"599_CR4","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.tcs.2012.09.006","volume":"511","author":"HL Bodlaender","year":"2013","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernel bounds for path and cycle problems. Theor. Comput. Sci. 511, 117\u2013136 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"35","key":"599_CR5","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":"3","key":"599_CR6","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discrete Appl. Math. 127(3), 415\u2013429 (2003)","journal-title":"Discrete Appl. Math."},{"key":"599_CR7","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.ic.2017.01.008","volume":"253","author":"Y Cao","year":"2017","unstructured":"Cao, Y.: Unit interval editing is fixed-parameter tractable. Inf. Comput. 253, 109\u2013126 (2017)","journal-title":"Inf. Comput."},{"issue":"3","key":"599_CR8","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/2629595","volume":"11","author":"Y Cao","year":"2015","unstructured":"Cao, Y., Marx, D.: Interval deletion is fixed-parameter tractable. ACM Trans. Algorithms 11(3), 21:1\u201321:35 (2015)","journal-title":"ACM Trans. Algorithms"},{"key":"599_CR9","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":"599_CR10","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 150\u2013159 (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"599_CR11","volume-title":"Graph Theory","author":"R Diestel","year":"2006","unstructured":"Diestel, R.: Graph Theory. Springer, Berlin (2006)"},{"key":"599_CR12","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":"599_CR13","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1965-035-8","volume":"17","author":"P Erd\u00f6s","year":"1965","unstructured":"Erd\u00f6s, P., P\u00f3sa, L.: On independent circuits contained in a graph. Can. J. Math. 17, 347\u2013352 (1965)","journal-title":"Can. J. Math."},{"issue":"3","key":"599_CR14","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1145\/44483.44491","volume":"35","author":"MR Fellows","year":"1988","unstructured":"Fellows, M.R., Langston, M.A.: Nonconstructive tools for proving polynomial-time decidability. J. ACM 35(3), 727\u2013739 (1988)","journal-title":"J. ACM"},{"issue":"4","key":"599_CR15","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1007\/s00224-009-9167-9","volume":"45","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F.A., Saurabh, S.: The complexity ecology of parameters: an illustration using bounded max leaf number. Theory Comput. Syst. 45(4), 822\u2013848 (2009)","journal-title":"Theory Comput. Syst."},{"key":"599_CR16","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"4","key":"599_CR17","doi-asserted-by":"publisher","first-page":"1964","DOI":"10.1137\/12089051X","volume":"27","author":"FV Fomin","year":"2013","unstructured":"Fomin, F.V., Saurabh, S., Villanger, Y.: A polynomial kernel for proper interval vertex deletion. SIAM J. Discrete Math. 27(4), 1964\u20131976 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"599_CR18","volume-title":"Algorithmic Graph Theory for Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory for Perfect Graphs. Springer, Berlin (2004)"},{"issue":"1","key":"599_CR19","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s006070170039","volume":"66","author":"V Guruswami","year":"2001","unstructured":"Guruswami, V., Pandu Rangan, C., Chang, M.S., Chang, G.J., Wong, C.K.: The $$K_r$$-packing problem. Computing 66(1), 79\u201389 (2001)","journal-title":"Computing"},{"issue":"2","key":"599_CR20","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00224-010-9262-y","volume":"48","author":"G Gutin","year":"2011","unstructured":"Gutin, G., Kim, E.J., Lampis, M., Mitsou, V.: Vertex cover problem parameterized above and below tight bounds. Theory Comput. Syst. 48(2), 402\u2013410 (2011)","journal-title":"Theory Comput. Syst."},{"key":"599_CR21","doi-asserted-by":"crossref","unstructured":"Gutin, G., Yeo, A.: Constraint satisfaction problems parameterized above or below tight bounds: a Survey. In: The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, pp. 257\u2013286 (2012)","DOI":"10.1007\/978-3-642-30891-8_14"},{"key":"599_CR22","unstructured":"Jansen, B.M.P.: The power of data reduction: kernels for fundamental graph problems. Ph.D. thesis, Utrecht University, The Netherlands (2013)"},{"issue":"3","key":"599_CR23","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","volume":"34","author":"BMP Jansen","year":"2013","unstructured":"Jansen, B.M.P., Fellows, M.R., Rosamond, F.A.: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3), 541\u2013566 (2013)","journal-title":"Eur. J. Comb."},{"issue":"4","key":"599_CR24","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1109\/TST.2014.6867520","volume":"19","author":"BMP Jansen","year":"2014","unstructured":"Jansen, B.M.P., Raman, V., Vatshelle, M.: Parameter ecology for feedback vertex set. Tsinghua Sci. Technol. 19(4), 387\u2013409 (2014)","journal-title":"Tsinghua Sci. Technol."},{"key":"599_CR25","unstructured":"Ke, Y., Cao, Y., Ouyang, X., Wang, J.: Unit interval vertex deletion: fewer vertices are relevant. \n                    arXiv:1607.01162\n                    \n                   (2016)"},{"key":"599_CR26","unstructured":"Kloks, T.: Packing interval graphs with vertex-disjoint triangles. CoRR, abs\/1202.1041 (2012)"},{"key":"599_CR27","unstructured":"Lokshtanov, D., Mouawad, A., Saurabh, S., Zehavi, M.: Packing cycles faster than Erd\u00f6s-P\u00f3sa. To appear in ICALP (2017)"},{"issue":"2","key":"599_CR28","doi-asserted-by":"publisher","first-page":"15:1","DOI":"10.1145\/2566616","volume":"11","author":"D Lokshtanov","year":"2014","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. ACM Trans. Algorithms 11(2), 15:1\u201315:31 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"599_CR29","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Panolan, F., Sridharan, R., Saurabh, S.: Lossy kernelization. To appear in STOC (2017)","DOI":"10.1145\/3055399.3055456"},{"issue":"7","key":"599_CR30","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0898-1221(93)90308-I","volume":"25","author":"PJ Looges","year":"1993","unstructured":"Looges, P.J., Olariu, S.: Optimal greedy algorithms for indifference graphs. Comput. Math. Appl. 25(7), 15\u201325 (1993)","journal-title":"Comput. Math. Appl."},{"issue":"8","key":"599_CR31","doi-asserted-by":"publisher","first-page":"1455","DOI":"10.1016\/j.disc.2007.07.100","volume":"308","author":"G Mani\u0107","year":"2008","unstructured":"Mani\u0107, G., Wakabayashi, Y.: Packing triangles in low degree graphs and indifference graphs. Discrete Math. 308(8), 1455\u20131471 (2008)","journal-title":"Discrete Math."},{"key":"599_CR32","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719802","volume-title":"Topics in Intersection Graph Theory. Society for Industrial and Applied Mathematics","author":"T McKee","year":"1999","unstructured":"McKee, T., McMorris, F.: Topics in Intersection Graph Theory. Society for Industrial and Applied Mathematics. SIAM, Philadelphia (1999)"},{"key":"599_CR33","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 182\u2013191 (1995)"},{"key":"599_CR34","doi-asserted-by":"crossref","unstructured":"van Bevern, R., Komusiewicz, C., Moser, H., Niedermeier, R.: Measuring indifference: unit interval vertex deletion. In: Proceedings of the 36th International Conference on Graph-Theoretic Concepts in Computer Science, WG\u201910, pp. 232\u2013243. Springer (2010)","DOI":"10.1007\/978-3-642-16926-7_22"},{"issue":"4","key":"599_CR35","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1007\/s00453-012-9661-3","volume":"65","author":"P van\u2019t Hof","year":"2013","unstructured":"van\u2019t Hof, P., Villanger, Y.: Proper interval vertex deletion. Algorithmica 65(4), 845\u2013867 (2013)","journal-title":"Algorithmica"},{"key":"599_CR36","first-page":"139","volume-title":"Proof Techniques in Graph Theory","author":"FS Roberts","year":"1969","unstructured":"Roberts, F.S.: Indifference graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory, pp. 139\u2013146. Academic Press, New York (1969)"},{"issue":"1","key":"599_CR37","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1111\/j.1749-6632.1979.tb17778.x","volume":"328","author":"FS Roberts","year":"1979","unstructured":"Roberts, F.S.: Indifference and seriation. Ann. N. Y. Acad. Sci. 328(1), 173\u2013182 (1979)","journal-title":"Ann. N. Y. Acad. Sci."},{"issue":"1","key":"599_CR38","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00599-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00599-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00599-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,19]],"date-time":"2020-06-19T23:06:17Z","timestamp":1592607977000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00599-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,21]]},"references-count":38,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["599"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00599-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,21]]},"assertion":[{"value":"4 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}