{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:02Z","timestamp":1740109382727,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T00:00:00Z","timestamp":1711929600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T00:00:00Z","timestamp":1711929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006764","name":"Technische Universit\u00e4t Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006764","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the problem of placing wildlife crossings, such as green bridges, over human-made obstacles to challenge habitat fragmentation. The main task herein is, given a graph describing habitats or routes of wildlife animals and possibilities of building green bridges, to find a low-cost placement of green bridges that connects the habitats. We develop three problem models for this task and study them from a computational complexity and parameterized algorithmics perspective.<\/jats:p>","DOI":"10.1007\/s00224-023-10157-5","type":"journal-article","created":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T09:12:10Z","timestamp":1711962730000},"page":"1312-1338","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Placing Green Bridges Optimally, with a Multivariate Analysis"],"prefix":"10.1007","volume":"68","author":[{"given":"Till","family":"Fluschnik","sequence":"first","affiliation":[]},{"given":"Leon","family":"Kellerhals","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,1]]},"reference":[{"key":"10157_CR1","doi-asserted-by":"publisher","unstructured":"Agarwal, D., Ara\u00fajo, J.C.S., Caillouet, C., Cazals, F., Coudert, D., P\u00e9rennes, S.: Connectivity inference in mass spectrometry based structure determination. In: Proc. 21st ESA, vol. 8125, pp. 289\u2013300. (2013). https:\/\/doi.org\/10.1007\/978-3-642-40450-4_25","DOI":"10.1007\/978-3-642-40450-4_25"},{"issue":"2","key":"10157_CR2","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). https:\/\/doi.org\/10.1007\/s10878-013-9603-2","journal-title":"J. Comb. Optim."},{"key":"10157_CR3","doi-asserted-by":"publisher","unstructured":"Bateni, M., Hajiaghayi, M.T., Marx, D.: Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. J. ACM 58(5), 21:1\u201321:37. (2011). https:\/\/doi.org\/10.1145\/2027216.2027219","DOI":"10.1145\/2027216.2027219"},{"key":"10157_CR4","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.jda.2011.12.009","volume":"14","author":"U Brandes","year":"2012","unstructured":"Brandes, U., Cornelsen, S., Pampel, B., Sallaberry, A.: Path-based supports for hypergraphs. J. Discrete Algorithms 14, 248\u2013261 (2012). https:\/\/doi.org\/10.1016\/j.jda.2011.12.009","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"10157_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/140955057","volume":"29","author":"J Chen","year":"2015","unstructured":"Chen, J., Komusiewicz, C., Niedermeier, R., Sorge, M., Such\u00fd, O., Weller, M.: Polynomial-time data reduction for the subset interconnection design problem. SIAM J. Discrete Math. 29(1), 1\u201325 (2015). https:\/\/doi.org\/10.1137\/140955057","journal-title":"SIAM J. Discrete Math."},{"key":"10157_CR6","doi-asserted-by":"publisher","unstructured":"Chockler, G.V., Melamed, R., Tock, Y., Vitenberg, R.: Constructing scalable overlays for pub-sub with many topics. In: Proc. of 26th PODC, pp. 109\u2013118. (2007). https:\/\/doi.org\/10.1145\/1281100.1281118","DOI":"10.1145\/1281100.1281118"},{"key":"10157_CR7","unstructured":"Conitzer, V., Derryberry, J., Sandholm, T.: Combinatorial auctions with structured item graphs. In: Proc. of 8th AAAI, pp. 212\u2013218. (2004). http:\/\/www.aaai.org\/Library\/AAAI\/2004\/aaai04-034.php"},{"key":"10157_CR8","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"3","key":"10157_CR9","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1002\/net.20003","volume":"43","author":"G Dahl","year":"2004","unstructured":"Dahl, G., Johannessen, B.: The 2-path network problem. Networks 43(3), 190\u2013199 (2004). https:\/\/doi.org\/10.1002\/net.20003","journal-title":"Networks"},{"key":"10157_CR10","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th Edition, Graduate texts in mathematics, vol. 173, Springer (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"10157_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.12.012","volume":"840","author":"W Ding","year":"2020","unstructured":"Ding, W., Qiu, K.: A 2-approximation algorithm and beyond for the minimum diameter k-steiner forest problem. Theor. Comput. Sci. 840, 1\u201315 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2019.12.012","journal-title":"Theor. Comput. Sci."},{"key":"10157_CR12","doi-asserted-by":"publisher","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and ids. ACM Trans. Algorithms 11(2), 13:1\u201313:20. (2014). https:\/\/doi.org\/10.1145\/2650261","DOI":"10.1145\/2650261"},{"issue":"1","key":"10157_CR13","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0166-218X(86)90010-7","volume":"14","author":"D Du","year":"1986","unstructured":"Du, D.: An optimization problem on graphs. Discret. Appl. Math. 14(1), 101\u2013104 (1986). https:\/\/doi.org\/10.1016\/0166-218X(86)90010-7","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"10157_CR14","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01096768","volume":"6","author":"D Du","year":"1995","unstructured":"Du, D., Kelley, D.F.: On complexity of subset interconnection designs. J. Glob. Optim. 6(2), 193\u2013205 (1995). https:\/\/doi.org\/10.1007\/BF01096768","journal-title":"J. Glob. Optim."},{"issue":"4","key":"10157_CR15","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0401042","volume":"1","author":"D Du","year":"1988","unstructured":"Du, D., Miller, Z.: Matroids and subset interconnection design. SIAM J. Discrete Math. 1(4), 416\u2013424 (1988). https:\/\/doi.org\/10.1137\/0401042","journal-title":"SIAM J. Discrete Math."},{"key":"10157_CR16","doi-asserted-by":"publisher","unstructured":"Fan, H., Hundt, C., Wu, Y., Ernst, J.: Algorithms and implementation for interconnection graph problem. In: Proc. 2nd COCOA, vol. 5165, pp. 201\u2013210. (2008). https:\/\/doi.org\/10.1007\/978-3-540-85097-7_19","DOI":"10.1007\/978-3-540-85097-7_19"},{"key":"10157_CR17","unstructured":"Fox, M., Poole, D. (eds.): Proc. of 24th AAAI. AAAI Press (2010)"},{"issue":"2","key":"10157_CR18","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.jda.2009.05.002","volume":"8","author":"E Gassner","year":"2010","unstructured":"Gassner, E.: The steiner forest problem revisited. J. Discrete Algorithms 8(2), 154\u2013163 (2010). https:\/\/doi.org\/10.1016\/j.jda.2009.05.002","journal-title":"J. Discrete Algorithms"},{"key":"10157_CR19","doi-asserted-by":"publisher","unstructured":"Gionis, A., Rozenshtein, P., Tatti, N., Terzi, E.: Community-aware network sparsification. In: Proc of SDM, pp. 426\u2013434. (2017). https:\/\/doi.org\/10.1137\/1.9781611974973.48","DOI":"10.1137\/1.9781611974973.48"},{"key":"10157_CR20","doi-asserted-by":"publisher","unstructured":"Gomes, C.P.: Challenges for constraint reasoning and optimization in computational sustainability. In: I.P. Gent (ed.) Proc. of 15th CP, Lecture Notes in Computer Science, vol. 5732, pp. 2\u20134, Springer. (2009). https:\/\/doi.org\/10.1007\/978-3-642-04244-7_2","DOI":"10.1007\/978-3-642-04244-7_2"},{"issue":"4","key":"10157_CR21","first-page":"5","volume":"39","author":"CP Gomes","year":"2009","unstructured":"Gomes, C.P.: Computational sustainability: Computational methods for a sustainable environment, economy, and society. Bridge 39(4), 5\u201313 (2009)","journal-title":"Bridge"},{"key":"10157_CR22","unstructured":"van\u00a0der Grift, E., Seiler, A., Rosell, C., Simeonova, V.: Safe roads for wildlife and people: final report of the saferoad project. Tech. Rep., Conference of European Directors of Roads. (2017). https:\/\/www.saferoad-cedr.org\/upload_mm\/4\/6\/b\/80eb4659-f6e6-4327-8358-f692b98f3419_CEDR_finalreport.pdf"},{"key":"10157_CR23","doi-asserted-by":"publisher","unstructured":"Herkenrath, M., Fluschnik, T., Grothe, F., Kellerhals, L.: Placing green bridges optimally, with habitats inducing cycles. In: Proc. of 31st IJCAI, pp. 3825\u20133831. (2022). https:\/\/doi.org\/10.24963\/ijcai.2022\/531","DOI":"10.24963\/ijcai.2022\/531"},{"key":"10157_CR24","unstructured":"Herrendorf, E.: On the complexity of community-aware network sparsification. Master\u2019s thesis, Universit\u00e4 Marburg. (2022). https:\/\/www.uni-marburg.de\/de\/fb12\/arbeitsgruppen\/algorith\/forschung\/master-emanuel-2.pdf"},{"key":"10157_CR25","doi-asserted-by":"crossref","unstructured":"Huijser, M.P., Duffield, J.W., Clevenger, A.P., Ament, R.J., McGowen, P.T.: Cost-benefit analyses of mitigation measures aimed at reducing collisions with large ungulates in the united states and canada: a decision support tool. Ecol. Soc. 14(2). (2009). http:\/\/www.jstor.org\/stable\/26268301","DOI":"10.5751\/ES-03000-140215"},{"key":"10157_CR26","unstructured":"Huijser, M.P., McGowan, P., Hardy, A., Kociolek, A., Clevenger, A., Smith, D., Ament, R., et\u00a0al.: Wildlife-vehicle collision reduction study: Report to congress. (2008). https:\/\/www.fhwa.dot.gov\/publications\/research\/safety\/08034\/08034.pdf"},{"key":"10157_CR27","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.tcs.2021.05.020","volume":"904","author":"EJ Kim","year":"2022","unstructured":"Kim, E.J., Milanic, M., Monnot, J., Picouleau, C.: Complexity and algorithms for constant diameter augmentation problems. Theor. Comput. Sci. 904, 15\u201326 (2022). https:\/\/doi.org\/10.1016\/j.tcs.2021.05.020","journal-title":"Theor. Comput. Sci."},{"key":"10157_CR28","doi-asserted-by":"crossref","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc. 7, 48\u201350. (1956). https:\/\/doi.org\/10.1090\/S0002-9939-1956-0078686-7","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"10157_CR29","doi-asserted-by":"crossref","unstructured":"Lai, K.J., Gomes, C.P., Schwartz, M.K., McKelvey, K.S., Calkin, D.E., Montgomery, C.A.: The steiner multigraph problem: Wildlife corridor design for multiple species. In: Proc. of 25th AAAI. AAAI Press. (2011). http:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI11\/paper\/view\/3768","DOI":"10.1609\/aaai.v25i1.7809"},{"key":"10157_CR30","doi-asserted-by":"publisher","unstructured":"LeBras, R., Dilkina, B., Xue, Y., Gomes, C.P., McKelvey, K.S., Schwartz, M.K., Montgomery, C.A.: Robust network design for multispecies conservation. In: Proc. of 27th AAAI, pp. 1305\u20131312. (2013). https:\/\/doi.org\/10.1609\/aaai.v27i1.8491","DOI":"10.1609\/aaai.v27i1.8491"},{"issue":"1","key":"10157_CR31","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1002\/net.3230110110","volume":"11","author":"J Plesn\u00edk","year":"1981","unstructured":"Plesn\u00edk, J.: The complexity of designing a network with minimum diameter. Netw. 11(1), 77\u201385 (1981). https:\/\/doi.org\/10.1002\/net.3230110110","journal-title":"Netw."},{"issue":"2","key":"10157_CR32","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/S0895480194266331","volume":"9","author":"R Ravi","year":"1996","unstructured":"Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., Ravi, S.S.: Spanning trees - short or small. SIAM J. Discret. Math. 9(2), 178\u2013200 (1996). https:\/\/doi.org\/10.1137\/S0895480194266331","journal-title":"SIAM J. Discret. Math."},{"key":"10157_CR33","doi-asserted-by":"crossref","unstructured":"Van\u00a0der Ree, R., Heinze, D., McCarthy, M., Mansergh, I.: Wildlife tunnel enhances population viability. Ecol. Soc. 14(2). (2009). http:\/\/www.ecologyandsociety.org\/vol14\/iss2\/art7\/","DOI":"10.5751\/ES-02957-140207"},{"issue":"4","key":"10157_CR34","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1002\/net.3230160408","volume":"16","author":"MB Richey","year":"1986","unstructured":"Richey, M.B., Parker, R.G.: On multiple steiner subgraph problems. Netw. 16(4), 423\u2013438 (1986). https:\/\/doi.org\/10.1002\/net.3230160408","journal-title":"Netw."},{"key":"10157_CR35","unstructured":"Rossi, F. (ed.): IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013. IJCAI\/AAAI. (2013). http:\/\/ijcai.org\/proceedings\/2013"},{"key":"10157_CR36","doi-asserted-by":"crossref","unstructured":"Sawaya, M.A., Kalinowski, S.T., Clevenger, A.P.: Genetic connectivity for two bear species at wildlife crossing structures in banff national park. Proceedings of the Royal Society B: Biological Sciences 281(1780), 20131705. (2014). https:\/\/www.ncbi.nlm.nih.gov\/pmc\/articles\/PMC4027379\/","DOI":"10.1098\/rspb.2013.1705"},{"key":"10157_CR37","unstructured":"Shilling, F., Waetjen, D., Porter, G., Short, C., Karcs, M., Honigman, T., Mejrano, M., Mohabir, G., Jyaw, M., Jones, A., Vickers, W., Harrold, K.: From wildlife-vehicle conflict to solutions for california drivers & animals. Tech. Rep., Road Ecology Center, UC Davis. (2021). https:\/\/roadecology.ucdavis.edu\/resources\/california-wildlife-vehicle-collision-hotspots-2021"},{"issue":"2","key":"10157_CR38","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22(2), 215\u2013225 (1975). https:\/\/doi.org\/10.1145\/321879.321884","journal-title":"J. ACM"},{"key":"10157_CR39","doi-asserted-by":"publisher","unstructured":"Zheng, R., Luo, Z., Yan, B.: Exploiting time-series image-to-image translation to expand the range of wildlife habitat analysis. In: Proc. of 33rd AAAI, pp. 825\u2013832. AAAI Press. (2019). https:\/\/doi.org\/10.1609\/aaai.v33i01.3301825","DOI":"10.1609\/aaai.v33i01.3301825"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10157-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10157-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10157-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T09:53:19Z","timestamp":1729849999000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10157-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,1]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10157"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10157-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,4,1]]},"assertion":[{"value":"22 November 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}