{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:42Z","timestamp":1740109242823,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,10,28]],"date-time":"2016-10-28T00:00:00Z","timestamp":1477612800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DAPA (NI 369\/12)","PREMOD (KR 4286\/1)"],"award-info":[{"award-number":["DAPA (NI 369\/12)","PREMOD (KR 4286\/1)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1007\/s00453-016-0231-y","type":"journal-article","created":{"date-parts":[[2016,10,28]],"date-time":"2016-10-28T08:51:53Z","timestamp":1477644713000},"page":"96-138","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Kernelization and Approximation for the Vector Connectivity Problem"],"prefix":"10.1007","volume":"79","author":[{"given":"Stefan","family":"Kratsch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Sorge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,28]]},"reference":[{"key":"231_CR1","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. In: 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u00a0\u201909), pp. 629\u2013638. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.46"},{"key":"231_CR2","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. CoRR, abs\/0904.0727v3, (2013). URL \n                        http:\/\/arxiv.org\/abs\/0904.0727"},{"issue":"1","key":"231_CR3","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"231_CR4","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1002\/net.21545","volume":"63","author":"E Boros","year":"2014","unstructured":"Boros, E., Heggernes, P., van \u2019t Hof, P., Milanic, M.: Vector connectivity in graphs. Networks 63(4), 277\u2013285 (2014)","journal-title":"Networks"},{"key":"231_CR5","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1137\/15M1032077","volume":"45","author":"R Chitnis","year":"2016","unstructured":"Chitnis, R., Cygan, M., Hajiaghayi, M., Pilipczuk, M., Pilipczuk, M.: Designing FPT algorithms for cut problems using randomized contractions. SIAM J. Comput. 45, 1171\u20131229 (2016)","journal-title":"SIAM J. Comput."},{"key":"231_CR6","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.tcs.2015.04.032","volume":"591","author":"F Cicalese","year":"2015","unstructured":"Cicalese, F., Milanic, M., Rizzi, R.: On the complexity of the vector connectivity problem. Theoret. Comput. Sci. 591, 60\u201371 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"231_CR7","doi-asserted-by":"crossref","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":"231_CR8","volume-title":"Graph Theory, Volume 173 of Graduate Texts in Mathematics","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, Volume 173 of Graduate Texts in Mathematics, 4th edn. Springer, Berlin (2010)","edition":"4"},{"issue":"2","key":"231_CR9","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and ids. ACM Trans. Algorithms 11(2), 13:1\u201313:20 (2014). doi:\n                        10.1145\/2650261","journal-title":"ACM Trans. Algorithms"},{"key":"231_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"R\u00a0G Downey","year":"2013","unstructured":"Downey, R\u00a0.G., Fellows, M\u00a0.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"key":"231_CR11","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"231_CR12","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a0\u201910), pp. 503\u2013510. SIAM (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"231_CR13","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In: Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u00a0\u201913, volume\u00a020 of LIPIcs, pp. 92\u2013103. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013)"},{"key":"231_CR14","volume-title":"Facility Location: Applications and Theory","author":"H\u00a0W Hamacher","year":"2002","unstructured":"Hamacher, H\u00a0.W., Drezner, Z.: Facility Location: Applications and Theory. Springer, Berlin (2002)"},{"key":"231_CR15","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1017\/S0963548399004034","volume":"8","author":"J Harant","year":"1999","unstructured":"Harant, J., Pruchnewski, A., Voigt, M.: On dominating sets and independent sets of graphs. Comb. Probab. Comput. 8, 547\u2013553 (1999)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"231_CR16","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1007\/s00453-014-9910-8","volume":"71","author":"D Hermelin","year":"2015","unstructured":"Hermelin, D., Kratsch, S., Soltys, K., Wahlstr\u00f6m, M., Wu, X.: A completeness theory for polynomial (Turing) kernelization. Algorithmica 71(3), 702\u2013730 (2015)","journal-title":"Algorithmica"},{"key":"231_CR17","volume-title":"Extremal Combinatorics\u2014With Applications in Computer Science. Texts in Theoretical Computer Science","author":"S Jukna","year":"2001","unstructured":"Jukna, S.: Extremal Combinatorics\u2014With Applications in Computer Science. Texts in Theoretical Computer Science. Springer, Berlin (2001)"},{"key":"231_CR18","doi-asserted-by":"crossref","unstructured":"Kim, E.J., Langer, A., Paul, C., Reidl, F., Rossmanith, P., Sau, I., Sikdar, S.: Linear kernels and single-exponential algorithms via protrusion decompositions. In: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP\u00a0\u201913), volume 7965 of Lecture Notes in Computer Science, pp. 613\u2013624. Springer (2013)","DOI":"10.1007\/978-3-642-39206-1_52"},{"key":"231_CR19","unstructured":"Kratsch, S., Sorge, M.: On kernelization and approximation for the vector connectivity problem. In: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915), volume\u00a043 of LIPIcs, pp. 377\u2013388. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)"},{"key":"231_CR20","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: new tools for kernelization. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u00a0\u201912), pp. 450\u2013459. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.46"},{"issue":"44","key":"231_CR21","doi-asserted-by":"crossref","first-page":"4471","DOI":"10.1016\/j.tcs.2009.07.027","volume":"410","author":"D Marx","year":"2009","unstructured":"Marx, D.: A parameterized view on matroid optimization problems. Theoret. Comput. Sci. 410(44), 4471\u20134479 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"231_CR22","doi-asserted-by":"crossref","first-page":"30:1","DOI":"10.1145\/2500119","volume":"9","author":"D Marx","year":"2013","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4), 30:1\u201330:35 (2013)","journal-title":"ACM Trans. Algorithms"},{"key":"231_CR23","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"231_CR24","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001","volume-title":"Matroid Theory","author":"J Oxley","year":"2011","unstructured":"Oxley, J.: Matroid Theory. Oxford University Press, Oxford (2011)"},{"issue":"1","key":"231_CR25","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0022-247X(68)90163-7","volume":"22","author":"H Perfect","year":"1968","unstructured":"Perfect, H.: Applications of Menger\u2019s graph theorem. J. Math. Anal. Appl. 22(1), 96\u2013111 (1968)","journal-title":"J. Math. Anal. Appl."},{"key":"231_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84800-070-4","volume-title":"The Algorithm Design Manual","author":"S Skiena","year":"2008","unstructured":"Skiena, S.: The Algorithm Design Manual, 2nd edn. Springer, Berlin (2008)","edition":"2"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0231-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0231-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0231-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,7,18]],"date-time":"2017-07-18T12:21:56Z","timestamp":1500380516000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0231-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,28]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["231"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0231-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,10,28]]}}}