{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T12:17:39Z","timestamp":1742991459394,"version":"3.40.3"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031389054"},{"type":"electronic","value":"9783031389061"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-38906-1_39","type":"book-chapter","created":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:05:14Z","timestamp":1690473914000},"page":"588-604","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An ETH-Tight Algorithm for\u00a0Bidirected Steiner Connectivity"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,28]]},"reference":[{"key":"39_CR1","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Gutin, G.Z.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer, Berlin (2008). Incorporated","DOI":"10.1007\/978-1-84800-998-1"},{"key":"39_CR2","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ic.2012.10.007","volume":"222","author":"P Berman","year":"2013","unstructured":"Berman, P., Bhattacharyya, A., Makarychev, K., Raskhodnikova, S., Yaroslavtsev, G.: Approximation algorithms for spanner problems and directed Steiner forest. Inf. Comput. 222, 93\u2013107 (2013)","journal-title":"Inf. Comput."},{"issue":"4","key":"39_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"MW Bern","year":"1989","unstructured":"Bern, M.W., Plassmann, P.E.: The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32(4), 171\u2013176 (1989)","journal-title":"Inf. Process. Lett."},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets m\u00f6bius: fast subset convolution. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, 11\u201313 June 2007, pp. 67\u201374 (2007)","DOI":"10.1145\/1250790.1250801"},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1\u20136:33 (2013)","DOI":"10.1145\/2432622.2432628"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Even, G., Gupta, A., Segev, D.: Set connectivity problems in undirected graphs and the directed Steiner network problem. ACM Trans. Algorithms 7(2), 18:1\u201318:17 (2011)","DOI":"10.1145\/1921659.1921664"},{"issue":"3","key":"39_CR7","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1109\/26.20105","volume":"37","author":"W Chen","year":"1989","unstructured":"Chen, W., Huang, N.: The strongly connecting problem on multihop packet radio networks. IEEE Trans. Commun. 37(3), 293\u2013295 (1989)","journal-title":"IEEE Trans. Commun."},{"key":"39_CR8","doi-asserted-by":"publisher","unstructured":"Chitnis, R., Feldmann, A.E., Manurangsi, P.: Parameterized approximation algorithms for bidirected steiner network problems. ACM Trans. Algorithms 17(2), 12:1\u201312:68 (2021). https:\/\/doi.org\/10.1145\/3447584","DOI":"10.1145\/3447584"},{"key":"39_CR9","doi-asserted-by":"crossref","unstructured":"Chitnis, R.H., Hajiaghayi, M., Kortsarz, G.: Fixed-parameter and approximation algorithms: a new look. In: Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, 4\u20136 September 2013, Revised Selected Papers, pp. 110\u2013122 (2013)","DOI":"10.1007\/978-3-319-03898-8_11"},{"key":"39_CR10","doi-asserted-by":"crossref","unstructured":"Chitnis, R.H., Hajiaghayi, M., Marx, D.: Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions). In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, 5\u20137 January 2014, pp. 1782\u20131801 (2014)","DOI":"10.1137\/1.9781611973402.129"},{"key":"39_CR11","doi-asserted-by":"publisher","unstructured":"Chlamt\u00e1\u010d, E., Dinitz, M., Kortsarz, G., Laekhanukit, B.: Approximating spanners and directed Steiner forest: upper and lower bounds. ACM Trans. Algorithms (TALG) 16(3), 1\u201331(2020). https:\/\/doi.org\/10.1145\/3381451","DOI":"10.1145\/3381451"},{"issue":"3","key":"39_CR12","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2008.06.046","volume":"406","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: The Steiner tree problem on graphs: inapproximability results. Theor. Comput. Sci. 406(3), 207\u2013214 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"39_CR13","doi-asserted-by":"crossref","unstructured":"Cygan, M., et al.: On problems as hard as CNF-SAT. ACM Trans. Algorithms 12(3), 41:1\u201341:24 (2016)","DOI":"10.1145\/2925416"},{"key":"39_CR14","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th Ed. Graduate texts in mathematics, vol. 173. Springer, Cham (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"39_CR15","unstructured":"Dinur, I., Manurangsi, P.: ETH-hardness of approximating 2-CSPs and directed Steiner network. In: 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, 11\u201314 January 2018, Cambridge, MA, USA, pp. 36:1\u201336:20 (2018)"},{"key":"39_CR16","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Khanna, S.: Design networks with bounded pairwise distance. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1\u20134 May 1999, Atlanta, Georgia, USA, pp. 750\u2013759 (1999)","DOI":"10.1145\/301250.301447"},{"issue":"2","key":"39_CR17","doi-asserted-by":"publisher","first-page":"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), 1\u201320 (2014). https:\/\/doi.org\/10.1145\/2650261","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"39_CR18","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"SE Dreyfus","year":"1971","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1(3), 195\u2013207 (1971)","journal-title":"Networks"},{"issue":"2","key":"39_CR19","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/S0097539704441241","volume":"36","author":"J Feldman","year":"2006","unstructured":"Feldman, J., Ruhl, M.: The directed Steiner network problem is tractable for a constant number of terminals. SIAM J. Comput. 36(2), 543\u2013561 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"39_CR20","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/j.jcss.2011.05.009","volume":"78","author":"M Feldman","year":"2012","unstructured":"Feldman, M., Kortsarz, G., Nutov, Z.: Improved approximation algorithms for directed Steiner forest. J. Comput. Syst. Sci. 78(1), 279\u2013292 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"39_CR21","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1\u201329:60 (2016)","DOI":"10.1145\/2886094"},{"issue":"2","key":"39_CR22","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0210019","volume":"10","author":"GN Frederickson","year":"1981","unstructured":"Frederickson, G.N., J\u00e1J\u00e1, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10(2), 270\u2013283 (1981)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"39_CR23","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s00224-007-1324-4","volume":"41","author":"B Fuchs","year":"2007","unstructured":"Fuchs, B., Kern, W., M\u00f6lle, D., Richter, S., Rossmanith, P., Wang, X.: Dynamic programming for minimum Steiner trees. Theory Comput. Syst. 41(3), 493\u2013500 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"39_CR24","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1006\/jcss.1995.1022","volume":"50","author":"HN Gabow","year":"1995","unstructured":"Gabow, H.N.: A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci. 50(2), 259\u2013273 (1995). https:\/\/doi.org\/10.1006\/jcss.1995.1022","journal-title":"J. Comput. Syst. Sci."},{"key":"39_CR25","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Olver, N., Rothvo\u00df, T., Zenklusen, R.: Matroids and integrality gaps for hypergraphic Steiner tree relaxations. In: Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19\u201322 May 2012, pp. 1161\u20131176 (2012)","DOI":"10.1145\/2213977.2214081"},{"key":"39_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2018.03.001","volume":"97","author":"P Goyal","year":"2018","unstructured":"Goyal, P., Misra, P., Panolan, F., Philip, G., Saurabh, S.: Finding even subgraphs even faster. J. Comput. Syst. Sci. 97, 1\u201313 (2018). https:\/\/doi.org\/10.1016\/j.jcss.2018.03.001","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"39_CR27","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1137\/100794560","volume":"25","author":"J Guo","year":"2011","unstructured":"Guo, J., Niedermeier, R., Such\u00fd, O.: Parameterized complexity of arc-weighted directed Steiner problems. SIAM J. Discrete Math. 25(2), 583\u2013599 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"39_CR28","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85\u2013103. Springer, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"39_CR29","doi-asserted-by":"publisher","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: new tools for kernelization. J. ACM 67(3), 16:1\u201316:50 (2020). https:\/\/doi.org\/10.1145\/3390887","DOI":"10.1145\/3390887"},{"issue":"1","key":"39_CR30","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s10878-013-9637-5","volume":"30","author":"NX Lam","year":"2015","unstructured":"Lam, N.X., Nguyen, T.N., An, M.K., Huynh, D.T.: Dual power assignment optimization and fault tolerance in WSNS. J. Comb. Optim. 30(1), 120\u2013138 (2015)","journal-title":"J. Comb. Optim."},{"key":"39_CR31","doi-asserted-by":"publisher","unstructured":"Manurangsi, P., Rubinstein, A., Schramm, T.: The strongish planted clique hypothesis and its consequences. In: Lee, J.R. (ed.) 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 185, pp. 10:1\u201310:21. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2021.10","DOI":"10.4230\/LIPIcs.ITCS.2021.10"},{"issue":"4","key":"39_CR32","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1007\/s00453-012-9630-x","volume":"65","author":"J Nederlof","year":"2013","unstructured":"Nederlof, J.: Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica 65(4), 868\u2013884 (2013). https:\/\/doi.org\/10.1007\/s00453-012-9630-x","journal-title":"Algorithmica"},{"issue":"1","key":"39_CR33","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1006\/jagm.2000.1086","volume":"36","author":"HJ Pr\u00f6mel","year":"2000","unstructured":"Pr\u00f6mel, H.J., Steger, A.: A new approximation algorithm for the Steiner tree problem with performance ratio 5\/3. J. Algorithms 36(1), 89\u2013101 (2000)","journal-title":"J. Algorithms"},{"key":"39_CR34","doi-asserted-by":"crossref","unstructured":"Ramanathan, R., Hain, R.: Topology control of multihop wireless networks using transmit power adjustment. In: Proceedings IEEE INFOCOM 2000, The Conference on Computer Communications, Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Reaching the Promised Land of Communications, Tel Aviv, Israel, 26\u201330 March 2000, pp. 404\u2013413 (2000)","DOI":"10.1109\/INFCOM.2000.832213"},{"key":"39_CR35","unstructured":"Vetta, A.: Approximating the minimum strongly connected subgraph via a matching lower bound. In: Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 7\u20139 January 2001, Washington, DC, USA, pp. 417\u2013426 (2001)"},{"issue":"1\u20133","key":"39_CR36","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.tcs.2008.01.029","volume":"396","author":"C Wang","year":"2008","unstructured":"Wang, C., Park, M.A., Willson, J., Cheng, Y., Farago, A., Wu, W.: On approximate optimal dual power assignment for biconnectivity and edge-biconnectivity. Theor. Comput. Sci. 396(1\u20133), 180\u2013190 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"39_CR37","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.: An 11\/6-approximation algorithm for the network Steiner problem. Algorithmica 9(5), 463\u2013470 (1993)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-38906-1_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T05:03:57Z","timestamp":1729832637000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-38906-1_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031389054","9783031389061"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-38906-1_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"28 July 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Algorithms and Data Structures Symposium","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Montreal, QC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"92","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}