{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T18:02:25Z","timestamp":1784484145761,"version":"3.55.0"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032313478","type":"print"},{"value":"9783032313485","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T00:00:00Z","timestamp":1784505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T00:00:00Z","timestamp":1784505600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2027]]},"DOI":"10.1007\/978-3-032-31348-5_17","type":"book-chapter","created":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T17:29:46Z","timestamp":1784482186000},"page":"256-271","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Placing Green Bridges Optimally for\u00a0Robust Habitat Reconnection"],"prefix":"10.1007","author":[{"given":"Gero","family":"Ellmies","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2203-4386","authenticated-orcid":false,"given":"Till","family":"Fluschnik","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,20]]},"reference":[{"issue":"2","key":"17_CR1","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1007\/s10878-013-9603-2","volume":"29","author":"D Angluin","year":"2015","unstructured":"Angluin, D., Aspnes, J., Reyzin, L.: Network construction with subgraph connectivity constraints. J. Comb. Optim. 29(2), 418\u2013432 (2015)","journal-title":"J. Comb. Optim."},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Cheriyan, J., V\u00e9gh, L.A.: Approximating minimum-cost k-node connected subgraphs via independence-free graphs. In: Proceedings of the 54th FOCS, pp. 30\u201339. FOCS \u201913. IEEE Computer Society, USA (2013)","DOI":"10.1109\/FOCS.2013.12"},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.jda.2018.11.010","volume":"52\u201353","author":"N Cohen","year":"2018","unstructured":"Cohen, N., Havet, F., Mazauric, D., Sau, I., Watrigant, R.: Complexity dichotomies for the minimum $${F}$$-overlay problem. J. Discrete Algorithms 52\u201353, 133\u2013142 (2018)","journal-title":"J. Discrete Algorithms"},{"key":"17_CR4","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.dam.2020.12.010","volume":"292","author":"A Darmann","year":"2021","unstructured":"Darmann, A., D\u00f6cker, J.: On simplified NP-complete variants of Monotone 3-Sat. Discret. Appl. Math. 292, 45\u201358 (2021)","journal-title":"Discret. Appl. Math."},{"key":"17_CR5","unstructured":"Ellmies, G., Fluschnik, T.: Placing green bridges optimally for robust habitat reconnection. CoRR abs\/2602.19834 (2026)"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Ene, A., Vakilian, A.: Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements. In: Proceedings of the 46th STOC, pp. 754\u2013763. STOC \u201914. Association for Computing Machinery, New York, NY, USA (2014)","DOI":"10.1145\/2591796.2591837"},{"issue":"20","key":"17_CR7","doi-asserted-by":"publisher","first-page":"2742","DOI":"10.1016\/j.disc.2010.05.028","volume":"310","author":"H Fleischner","year":"2010","unstructured":"Fleischner, H., Sabidussi, G., Sarvanov, V.I.: Maximum independent sets in 3- and 4-regular Hamiltonian graphs. Discret. Math. 310(20), 2742\u20132749 (2010)","journal-title":"Discret. Math."},{"issue":"5","key":"17_CR8","doi-asserted-by":"publisher","first-page":"1312","DOI":"10.1007\/s00224-023-10157-5","volume":"68","author":"T Fluschnik","year":"2024","unstructured":"Fluschnik, T., Kellerhals, L.: Placing green bridges optimally, with a multivariate analysis. Theory Comput. Syst. 68(5), 1312\u20131338 (2024)","journal-title":"Theory Comput. Syst."},{"key":"17_CR9","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. Freeman, W. H (1979)"},{"issue":"4","key":"17_CR10","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Gionis, A., Rozenshtein, P., Tatti, N., Terzi, E.: Community-aware network sparsification. In: Chawla, N.V., Wang, W. (eds.) Proceedings of the 2017 SDM, pp. 426\u2013434. SIAM (2017)","DOI":"10.1137\/1.9781611974973.48"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Herkenrath, M., Fluschnik, T., Grothe, F., Kellerhals, L.: Placing green bridges optimally, with habitats inducing cycles. In: Proceedings of the 31st IJCAI, pp. 3825\u20133831 (2022)","DOI":"10.24963\/ijcai.2022\/531"},{"key":"17_CR13","unstructured":"Herrendorf, E., Komusiewicz, C., Morawietz, N., Sommer, F.: On the complexity of community-aware network sparsification. In: Kr\u00e1lovic, R., Kucera, A. (eds.) Proceedings of the 49th MFCS. LIPIcs, vol.\u00a0306, pp. 60:1\u201360:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024)"},{"issue":"1","key":"17_CR14","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"17_CR15","unstructured":"Wallisch, C., Fluschnik, T., Kellerhals, L.: Placing green bridges optimally, with close-range habitats in sparse graphs. CoRR abs\/2510.21540 (2025). To appear in the proceedings of AAMAS\u201926."}],"container-title":["Lecture Notes in Computer Science","Timeless Machines: Computability Across Eras"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-31348-5_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T17:29:47Z","timestamp":1784482187000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-31348-5_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,20]]},"ISBN":["9783032313478","9783032313485"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-31348-5_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,20]]},"assertion":[{"value":"20 July 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Trier","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":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 July 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}