{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T04:56:39Z","timestamp":1777006599411,"version":"3.51.4"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030794156","type":"print"},{"value":"9783030794163","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-79416-3_20","type":"book-chapter","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T18:03:46Z","timestamp":1623866626000},"page":"339-348","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Rooted k-Connectivity Problems in Quasi-bipartite Digraphs"],"prefix":"10.1007","author":[{"given":"Zeev","family":"Nutov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e1, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1\u20136:33 (2013). Preliminary version in STOC 2010","DOI":"10.1145\/2432622.2432628"},{"key":"20_CR2","unstructured":"Chan, C-H., Laekhanukit, B., Wei, H-T., Zhang, Y.: Polylogarithmic approximation algorithm for $$k$$-connected directed Steiner tree on quasi-bipartite graphs. In: APPROX\/RANDOM, pp. 63:1\u201363:20 (2020)"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Charikar, M., et al.: Approximation algorithms for directed Steiner problems. J. Algorithms 33(1), 73\u201391 (1999). Preliminary version in SODA 1998","DOI":"10.1006\/jagm.1999.1042"},{"key":"20_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-32512-0_9","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Ene, A., Vakilian, A.: Prize-collecting survivable network design in node-weighted graphs. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM -2012. LNCS, vol. 7408, pp. 98\u2013109. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32512-0_9"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Cheriyan, J., Laekhanukit, B., Naves, G., Vetta, A.: Approximating rooted steiner networks. ACM Trans. Algorithms 11(2):8:1\u20138:22 (2014). Preliminary version in SODA 2012","DOI":"10.1145\/2650183"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Even, G.: Recursive greedy methods. In: Gonzalez, T.F. (ed.), Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 1: Methologies and Traditional Applications, pp. 71\u201384. Chapman & Hall\/CRC (2018)","DOI":"10.1201\/9781351236423-5"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Laekhanukit, B.: An $$O(\\log ^2 k)$$-approximation algorithm for the $$k$$-vertex connected spanning subgraph problem. SIAM J. Comput. 41(5):1095\u20131109 (2012). Preliminary version in STOC 2008","DOI":"10.1137\/110855910"},{"issue":"1\u20132","key":"20_CR8","first-page":"63","volume":"41","author":"A Frank","year":"1979","unstructured":"Frank, A.: Kernel systems of directed graphs. Acta Sci. Math. (Szeged) 41(1\u20132), 63\u201376 (1979)","journal-title":"Acta Sci. Math. (Szeged)"},{"issue":"6","key":"20_CR9","doi-asserted-by":"publisher","first-page":"1242","DOI":"10.1016\/j.dam.2008.03.040","volume":"157","author":"A Frank","year":"2009","unstructured":"Frank, A.: Rooted $$k$$-connections in digraphs. Discret. Appl. Math. 157(6), 1242\u20131254 (2009)","journal-title":"Discret. Appl. Math."},{"key":"20_CR10","unstructured":"Friggstad, Z., K\u00f6nemann, J., Shadravan, M.: A logarithmic integrality gap bound for directed Steiner tree in quasi-bipartite graphs. In: SWAT, pp. 3:1\u20133:11 (2016)"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Fukunaga, T.: Spider covers for prize-collecting network activation problem. ACM Trans. Algorithms 13(4), 49:1\u201349:31 (2017). Preliminary version in SODA 2015","DOI":"10.1145\/3132742"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group steiner tree problem. J. Algorithms 37(1), 66\u201384 (2000). Preliminary version in SODA 1998","DOI":"10.1006\/jagm.2000.1096"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Ghuge, R., Nagarajan, V.: A quasi-polynomial algorithm for submodular tree orienteering in directed graphs. In: SODA, pp. 1039\u20131048 (2020)","DOI":"10.1137\/1.9781611975994.63"},{"key":"20_CR14","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: STOC, pp. 1161\u20131176 (2012)","DOI":"10.1145\/2213977.2214081"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Laekhanukit, B.: Surviving in directed graphs: a quasi-polynomial time polylogarithmic approximation for two-connected directed Steiner tree. In: STOC, pp. 420\u2013428 (2017)","DOI":"10.1145\/3055399.3055445"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Laekhanukit, B., Li, S.: $$O(\\log ^2 k\/ \\log \\log k)$$-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm. In: STOC, pp. 253\u2013264 (2019)","DOI":"10.1145\/3313276.3316349"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: STOC, pp. 585\u2013594 (2003)","DOI":"10.1145\/780542.780628"},{"issue":"1","key":"20_CR18","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1002\/1097-0037(200101)37:1<8::AID-NET2>3.0.CO;2-R","volume":"37","author":"CS Helvig","year":"2001","unstructured":"Helvig, C.S., Robins, G., Zelikovsky, A.: An improved approximation scheme for the group Steiner problem. Networks 37(1), 8\u201320 (2001)","journal-title":"Networks"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Hibi, T., Fujito, T.: Multi-rooted greedy approximation of directed Steiner trees with applications. Algorithmica 74(2), 778\u2013786 (2016). Preliminary version in WG 2012","DOI":"10.1007\/s00453-015-9973-1"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39\u201360 (2001). preliminary version in FOCS 1998","DOI":"10.1007\/s004930170004"},{"key":"20_CR21","doi-asserted-by":"crossref","unstructured":"Klein, P.N., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19(1), 104\u2013115 (1995). Preliminary version in IPCO 1993","DOI":"10.1006\/jagm.1995.1029"},{"key":"20_CR22","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Nutov, Z.: Approximating $$k$$-node connected subgraphs via critical graphs. SIAM J. Comput. 35(1), 247\u2013257 (2005). Preliminary version in STOC 2004","DOI":"10.1137\/S0097539703435753"},{"key":"20_CR23","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Nutov, Z.: Tight approximation algorithm for connectivity augmentation problems. J. Comput. Syst. Sci. 74(5), 662\u2013670 (2008). Preliminary version in ICALP 2006","DOI":"10.1016\/j.jcss.2007.05.002"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Nutov, Z.: Approximating source location and star survivable network problems. Theor. Comput. Sci. 674, 32\u201342 (2017). Preliminary version in WG 2015, pp. 203\u2013218","DOI":"10.1016\/j.tcs.2017.02.008"},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Peleg, D.: Approximating the weight of shallow Steiner trees. Discrete Appl. Math. 93(2\u20133), 265\u2013285 (1999). Preliminary version in SODA 1997","DOI":"10.1016\/S0166-218X(99)00111-0"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Laekhanukit, B.: Parameters of two-prover-one-round game and the hardness of connectivity problems. In: SODA, pp. 1626\u20131643 (2014)","DOI":"10.1137\/1.9781611973402.118"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"Lando, Y., Nutov, Z.: Inapproximability of survivable networks. Theor. Comput. Sci. 410(21\u201323), 2122\u20132125 (2009). Preliminary version in APPROX-RANDOM 2008","DOI":"10.1016\/j.tcs.2009.01.036"},{"key":"20_CR28","doi-asserted-by":"crossref","unstructured":"Nutov, Z.: Approximating minimum power covers of intersecting families and directed edge-connectivity problems. Theor. Comput. Sci. 411(26\u201328), 2502\u20132512 (2010). Preliminary version in APPROX-RANDOM 2006, pp. 236\u2013247","DOI":"10.1016\/j.tcs.2010.03.009"},{"key":"20_CR29","doi-asserted-by":"crossref","unstructured":"Nutov, Z.: Approximating Steiner networks with node-weights. SIAM J. Comput. 39(7), 3001\u20133022 (2010). Preliminary version in LATIN 2008, pp. 411\u2013422","DOI":"10.1137\/080729645"},{"key":"20_CR30","doi-asserted-by":"crossref","unstructured":"Nutov, Z.: Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions. ACM Trans. Algorithms 9(1), 1:1\u20131:16, 2012. Preliminary version in FOCS 2009, pp. 417\u2013426","DOI":"10.1145\/2390176.2390177"},{"key":"20_CR31","unstructured":"Nutov, Z.: Node-connectivity survivable network problems. In: Gonzalez, T.F. (ed.), Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 2: Contemporary and Emerging Applications, chapter 13. Chapman & Hall\/CRC (2018)"},{"key":"20_CR32","unstructured":"Rajagopalan, S., Vazirani, V.V.: On the bidirected cut relaxation for the metric Steiner tree problem. In: SODA, pp. 742\u2013751 (1999)"},{"issue":"1","key":"20_CR33","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF02523690","volume":"18","author":"A Zelikovsky","year":"1997","unstructured":"Zelikovsky, A.: A series of approximation algorithms for the acyclic directed steiner tree problem. Algorithmica 18(1), 99\u2013110 (1997)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79416-3_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T23:22:53Z","timestamp":1623972173000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79416-3_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030794156","9783030794163"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79416-3_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"17 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sochi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2021\/","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":"68","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":"28","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":"41% - 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":"9.2","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)"}}]}}