{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T00:00:16Z","timestamp":1740182416104,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,1,17]],"date-time":"2024-01-17T00:00:00Z","timestamp":1705449600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,17]],"date-time":"2024-01-17T00:00:00Z","timestamp":1705449600000},"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":["Oper. Res. Forum"],"DOI":"10.1007\/s43069-023-00285-6","type":"journal-article","created":{"date-parts":[[2024,1,17]],"date-time":"2024-01-17T10:02:16Z","timestamp":1705485736000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Rooted k-Connectivity Problems in Quasi-Bipartite Digraphs"],"prefix":"10.1007","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6629-3243","authenticated-orcid":false,"given":"Zeev","family":"Nutov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,17]]},"reference":[{"issue":"6","key":"285_CR1","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 (2009) Rooted $$k$$-connections in digraphs. Discret Appl Math 157(6):1242\u20131254","journal-title":"Discret Appl Math"},{"key":"285_CR2","unstructured":"Chan C-H, Laekhanukit B, Wei H-T, Zhang Y (2020) Polylogarithmic approximation algorithm for $$k$$-connected directed Steiner tree on quasi-bipartite graphs. In: APPROX\/RANDOM. pp 63:1\u201363:20"},{"key":"285_CR3","doi-asserted-by":"crossref","unstructured":"Kortsarz G, Nutov Z (2017) Approximating source location and star survivable network problems. Theor Comput Sci 674:32\u201342. Preliminary version in WG 2015, p. 203-218","DOI":"10.1016\/j.tcs.2017.02.008"},{"key":"285_CR4","doi-asserted-by":"crossref","unstructured":"Nutov Z (2010) Approximating minimum power covers of intersecting families and directed edge-connectivity problems. Theor Comput Sci 411(26-28):2502\u20132512. Preliminary version in APPROX-RANDOM 2006, p. 236-247","DOI":"10.1016\/j.tcs.2010.03.009"},{"key":"285_CR5","doi-asserted-by":"crossref","unstructured":"Klein PN, Ravi R (1995) A nearly best-possible approximation algorithm for node-weighted Steiner trees. J Algorithms 19(1):104\u2013115. Preliminary version in IPCO 1993","DOI":"10.1006\/jagm.1995.1029"},{"key":"285_CR6","doi-asserted-by":"crossref","unstructured":"Nutov Z (2010) Approximating Steiner networks with node-weights. SIAM J Comput 39(7):3001\u20133022. Preliminary version in LATIN 2008, p. 411-422","DOI":"10.1137\/080729645"},{"key":"285_CR7","doi-asserted-by":"crossref","unstructured":"Nutov Z (2012) Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions. ACM Trans Algorithms 9(1):1:1\u20131:16. Preliminary version in FOCS 2009, p. 417\u2013426","DOI":"10.1145\/2390176.2390177"},{"key":"285_CR8","doi-asserted-by":"crossref","unstructured":"Kortsarz G, Nutov Z (2005) Approximating $$k$$-node connected subgraphs via critical graphs. SIAM J Comput 35(1):247\u2013257. Preliminary version in STOC 2004","DOI":"10.1137\/S0097539703435753"},{"key":"285_CR9","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol J, Laekhanukit B (2012) An $$O(\\log ^2 k)$$-approximation algorithm for the $$k$$-vertex connected spanning subgraph problem. SIAM J Comput 41(5):1095\u20131109. Preliminary version in STOC 2008","DOI":"10.1137\/110855910"},{"key":"285_CR10","doi-asserted-by":"crossref","unstructured":"Fukunaga T (2017) Spider covers for prize-collecting network activation problem. ACM Trans Algorithms 13(4):49:1\u201349:31. Preliminary version in SODA 2015","DOI":"10.1145\/3132742"},{"key":"285_CR11","doi-asserted-by":"crossref","unstructured":"Chekuri C, Ene A, Vakilian A (2012) Prize-collecting survivable network design in node-weighted graphs. In: APPROX-RANDOM. pp 98\u2013109","DOI":"10.1007\/978-3-642-32512-0_9"},{"issue":"1","key":"285_CR12","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF02523690","volume":"18","author":"A Zelikovsky","year":"1997","unstructured":"Zelikovsky A (1997) A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica 18(1):99\u2013110","journal-title":"Algorithmica"},{"key":"285_CR13","doi-asserted-by":"crossref","unstructured":"Charikar M, Chekuri C, Cheung T-Y, Dai Z, Goel A, Guha S, Li M (1999) Approximation algorithms for directed Steiner problems. J Algorithms 33(1):73\u201391. Preliminary version in SODA 1998","DOI":"10.1006\/jagm.1999.1042"},{"key":"285_CR14","doi-asserted-by":"crossref","unstructured":"Kortsarz G, Peleg D (1999) Approximating the weight of shallow Steiner trees. Discrete Appl Math 93(2-3):265\u2013285. Preliminary version in SODA 1997","DOI":"10.1016\/S0166-218X(99)00111-0"},{"issue":"1","key":"285_CR15","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 CS, Robins G, Zelikovsky A (2001) An improved approximation scheme for the group Steiner problem. Networks 37(1):8\u201320","journal-title":"Networks"},{"key":"285_CR16","doi-asserted-by":"crossref","unstructured":"Grandoni F, Laekhanukit B, Li S (2019) $$O(\\log ^2 k\/ \\log \\log k)$$-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm. In: STOC. pp 253\u2013264","DOI":"10.1145\/3313276.3316349"},{"key":"285_CR17","doi-asserted-by":"crossref","unstructured":"Ghuge R, Nagarajan V (2020) A quasi-polynomial algorithm for submodular tree orienteering in directed graphs. In: SODA. p. 1039\u20131048","DOI":"10.1137\/1.9781611975994.63"},{"key":"285_CR18","doi-asserted-by":"crossref","unstructured":"Even G (2018) Recursive greedy methods. In: Gonzalez TF (ed) Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 1: Methologies and Traditional Applications. Chapman & Hall\/CRC, pp 71\u201384","DOI":"10.1201\/9781351236423-5"},{"key":"285_CR19","doi-asserted-by":"crossref","unstructured":"Grandoni F, Laekhanukit B (2017) Surviving in directed graphs: a quasi-polynomial time polylogarithmic approximation for two-connected directed Steiner tree. In: STOC. pp 420\u2013428","DOI":"10.1145\/3055399.3055445"},{"key":"285_CR20","doi-asserted-by":"crossref","unstructured":"Halperin E, Krauthgamer R (2003) Polylogarithmic inapproximability. In: STOC. pp 585\u2013594","DOI":"10.1145\/780542.780628"},{"key":"285_CR21","doi-asserted-by":"crossref","unstructured":"Garg N, Konjevod G, Ravi R (2000) A polylogarithmic approximation algorithm for the group Steiner tree problem. J Algorithms 37(1):66\u201384. Preliminary version in SODA 1998","DOI":"10.1006\/jagm.2000.1096"},{"key":"285_CR22","doi-asserted-by":"crossref","unstructured":"Byrka J, Grandoni F, Rothvo\u00df T, Sanit\u00e1 L (2013) Steiner tree approximation via iterative randomized rounding. J ACM 60(1):6:1\u20136:33. Preliminary version in STOC 2010","DOI":"10.1145\/2432622.2432628"},{"key":"285_CR23","doi-asserted-by":"crossref","unstructured":"Goemans MX, Olver N, Rothvo\u00df T, Zenklusen R (2012) Matroids and integrality gaps for hypergraphic Steiner tree relaxations. In: STOC. pp 1161\u20131176","DOI":"10.1145\/2213977.2214081"},{"key":"285_CR24","unstructured":"Rajagopalan S, Vazirani VV (1999) On the bidirected cut relaxation for the metric Steiner tree problem. In: SODA. pp 742\u2013751"},{"key":"285_CR25","unstructured":"Friggstad Z, K\u00f6nemann J, Shadravan M (2016) A logarithmic integrality gap bound for directed Steiner tree in quasi-bipartite graphs. In: SWAT. p 3:1\u20133:11"},{"key":"285_CR26","doi-asserted-by":"crossref","unstructured":"Hibi T, Fujito T (2016) Multi-rooted greedy approximation of directed Steiner trees with applications. Algorithmica 74(2):778\u2013786. Preliminary version in WG 2012","DOI":"10.1007\/s00453-015-9973-1"},{"key":"285_CR27","unstructured":"Nutov Z (2018) Node-connectivity survivable network problems. In: Gonzalez TF (ed) Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 2: Contemporary and Emerging Applications, chapter\u00a013. Chapman & Hall\/CRC"},{"key":"285_CR28","doi-asserted-by":"crossref","unstructured":"Jain K (2001) A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1):39\u201360. preliminary version in FOCS 1998","DOI":"10.1007\/s004930170004"},{"key":"285_CR29","doi-asserted-by":"crossref","unstructured":"Laekhanukit B (2014) Parameters of two-prover-one-round game and the hardness of connectivity problems. In: SODA. pp 1626\u20131643","DOI":"10.1137\/1.9781611973402.118"},{"key":"285_CR30","doi-asserted-by":"crossref","unstructured":"Kortsarz G, Nutov Z (2008) Tight approximation algorithm for connectivity augmentation problems. J Comput Syst Sci 74(5):662\u2013670. Preliminary version in ICALP 2006","DOI":"10.1016\/j.jcss.2007.05.002"},{"key":"285_CR31","doi-asserted-by":"crossref","unstructured":"Lando Y, Nutov Z (2009) Inapproximability of survivable networks. Theor Comput Sci 410(21-23):2122\u20132125. Preliminary version in APPROX-RANDOM 2008","DOI":"10.1016\/j.tcs.2009.01.036"},{"key":"285_CR32","doi-asserted-by":"crossref","unstructured":"Cheriyan J, Laekhanukit B, Naves G, Vetta A (2014) Approximating rooted Steiner networks. ACM Trans Algorithms 11(2):8:1\u20138:22. Preliminary version in SODA 2012","DOI":"10.1145\/2650183"},{"issue":"1\u20132","key":"285_CR33","first-page":"63","volume":"41","author":"A Frank","year":"1979","unstructured":"Frank A (1979) Kernel systems of directed graphs. Acta Sci Math (Szeged) 41(1\u20132):63\u201376","journal-title":"Acta Sci Math (Szeged)"}],"container-title":["Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-023-00285-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-023-00285-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-023-00285-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T06:22:48Z","timestamp":1711434168000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-023-00285-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,17]]},"references-count":33,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,3]]}},"alternative-id":["285"],"URL":"https:\/\/doi.org\/10.1007\/s43069-023-00285-6","relation":{},"ISSN":["2662-2556"],"issn-type":[{"type":"electronic","value":"2662-2556"}],"subject":[],"published":{"date-parts":[[2024,1,17]]},"assertion":[{"value":"26 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declares no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"10"}}