{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T13:10:02Z","timestamp":1749042602932,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531730"},{"type":"electronic","value":"9783662531747"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_16","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T14:50:06Z","timestamp":1470322206000},"page":"219-233","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of Computing the k-restricted Edge-connectivity of a Graph"],"prefix":"10.1007","author":[{"given":"Luis Pedro","family":"Montejano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0012-365X(96)00218-X","volume":"167","author":"C Balbuena","year":"1997","unstructured":"Balbuena, C., Carmona, A., F\u00e0brega, J., Fiol, M.A.: Extraconnectivity of graphs with large minimum degree and girth. Discrete Math. 167, 85\u2013100 (1997)","journal-title":"Discrete Math."},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION. Electron. Colloquium Comput. Complex. 8(26) (2001)","DOI":"10.1007\/3-540-45465-9_53"},{"key":"16_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/3-540-45465-9_53","volume-title":"Automata, Languages and Programming","author":"P Berman","year":"2002","unstructured":"Berman, P., Karpinski, M.: Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 623\u2013632. Springer, Heidelberg (2002)"},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","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":"1","key":"16_CR5","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/S0012-365X(02)00385-0","volume":"256","author":"P Bonsma","year":"2002","unstructured":"Bonsma, P., Ueffing, N., Volkmann, L.: Edge-cuts leaving components of order at least three. Discrete Math. 256(1), 431\u2013439 (2002)","journal-title":"Discrete Math."},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Chitnis, R.H., Cygan, M., Hajiaghayi, M., Pilipczuk, M., Pilipczuk, M.: Designing FPT algorithms for cut problems using randomized contractions. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 460\u2013469 (2012)","DOI":"10.1109\/FOCS.2012.29"},{"key":"16_CR7","unstructured":"Cygan, M., Fomin, F., Jansen, B.M., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M.: Open problems from School on Parameterized Algorithms and Complexity (2014). http:\/\/fptschool.mimuw.edu.pl\/opl.pdf"},{"key":"16_CR8","unstructured":"Cygan, M., Kowalik, L., Pilipczuk, M.: Open problems from Update Meeting on Graph Separation Problems (2013). http:\/\/worker2013.mimuw.edu.pl\/slides\/update-opl.pdf"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Minimum bisection is fixed parameter tractable. In: Proceedings of the 46th ACM Symposium on Theory of Computing (STOC), pp. 323\u2013332 (2014)","DOI":"10.1145\/2591796.2591852"},{"key":"16_CR10","volume-title":"Graph Theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Berlin (2005)","edition":"3"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S1571-0661(04)81014-4","volume":"78","author":"RG Downey","year":"2003","unstructured":"Downey, R.G., Estivill-Castro, V., Fellows, M.R., Prieto, E., Rosamond, F.A.: Cutting up is hard to do: the parameterized complexity of $$k$$ -cut and related problems. Electron. Notes Theor. Comput. Sci. 78, 209\u2013222 (2003)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"16_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0166-218X(85)90008-3","volume":"10","author":"ME Dyer","year":"1985","unstructured":"Dyer, M.E., Frieze, A.M.: On the complexity of partitioning graphs into connected subgraphs. Discrete Appl. Math. 10, 139\u2013153 (1985)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"16_CR14","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/0196-6774(86)90002-7","volume":"7","author":"ME Dyer","year":"1986","unstructured":"Dyer, M.E., Frieze, A.M.: Planar 3DM is NP-complete. J. Algorithms 7(2), 174\u2013184 (1986)","journal-title":"J. Algorithms"},{"issue":"4","key":"16_CR15","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0190(88)90025-7","volume":"27","author":"A-H Esfahanian","year":"1988","unstructured":"Esfahanian, A.-H., Hakimi, S.L.: On computing a conditional edge-connectivity of a graph. Inf. Process. Lett. 27(4), 195\u2013199 (1988)","journal-title":"Inf. Process. Lett."},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0012-365X(92)00475-7","volume":"127","author":"J F\u00e0brega","year":"1994","unstructured":"F\u00e0brega, J., Fiol, M.A.: Extraconnectivity of graphs with large girth. Discrete Math. 127, 163\u2013170 (1994)","journal-title":"Discrete Math."},{"key":"16_CR17","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"16_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York (1979)"},{"issue":"3","key":"16_CR19","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR20","unstructured":"Holtkamp, A.: Connectivity in Graphs and Digraphs. Maximizing vertex-, edge- and arc-connectivity with an emphasis on local connectivity properties. Ph.D. thesis, RWTH Aachen University (2013)"},{"issue":"9","key":"16_CR21","doi-asserted-by":"publisher","first-page":"1345","DOI":"10.1016\/j.dam.2012.01.022","volume":"160","author":"A Holtkamp","year":"2012","unstructured":"Holtkamp, A., Meierling, D., Montejano, L.P.: $$k$$ -restricted edge-connectivity in triangle-free graphs. Discrete Appl. Math. 160(9), 1345\u20131355 (2012)","journal-title":"Discrete Appl. Math."},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Thorup, M.: The minimum $$k$$ -way cut of bounded size is fixed-parameter tractable. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 160\u2013169 (2011)","DOI":"10.1109\/FOCS.2011.53"},{"key":"16_CR23","unstructured":"Kim, E.J., Oum, S., Paul, C., Sau, I., Thilikos, D.M.: The List Allocation Problem and Some of its Applications in Parameterized Algorithms. Manuscript submitted for publication (2015). http:\/\/www.lirmm.fr\/~sau\/Pubs\/LA.pdf"},{"issue":"3","key":"16_CR24","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"16_CR25","unstructured":"Marx, D., Pilipczuk, M.: Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask). In: Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 542\u2013553 (2014)"},{"key":"16_CR26","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pp. 182\u2013191 (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"key":"16_CR27","doi-asserted-by":"publisher","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)"},{"issue":"4","key":"16_CR28","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1145\/263867.263872","volume":"44","author":"M Stoer","year":"1997","unstructured":"Stoer, M., Wagner, F.: A simple min-cut algorithm. J. ACM 44(4), 585\u2013591 (1997)","journal-title":"J. ACM"},{"key":"16_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/978-3-642-45043-3_8","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"R Bevern van","year":"2013","unstructured":"van Bevern, R., Feldmann, A.E., Sorge, M., Such\u00fd, O.: On the parameterized complexity of computing graph bisections. In: Brandst\u00e4dt, A., Jansen, K., Reischuk, R. (eds.) WG 2013. LNCS, vol. 8165, pp. 76\u201387. Springer, Heidelberg (2013)"},{"key":"16_CR30","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1016\/j.disc.2009.10.014","volume":"310","author":"J Yuan","year":"2010","unstructured":"Yuan, J., Liu, A.: Sufficient conditions for $$\\lambda _k$$ -optimality in triangle-free graphs. Discrete Math. 310, 981\u2013987 (2010)","journal-title":"Discrete Math."},{"key":"16_CR31","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.disc.2005.04.020","volume":"304","author":"Z Zhang","year":"2005","unstructured":"Zhang, Z., Yuan, J.: A proof of an inequality concerning k-restricted edge-connectivity. Discrete Math. 304, 128\u2013134 (2005)","journal-title":"Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T12:53:10Z","timestamp":1749041590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"5 August 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Garching","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2015","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2015","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2015","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"41","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2015","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}