{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T13:24:48Z","timestamp":1758633888985,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,3,29]],"date-time":"2016-03-29T00:00:00Z","timestamp":1459209600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,3,29]],"date-time":"2016-03-29T00:00:00Z","timestamp":1459209600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CAREER 1053605"],"award-info":[{"award-number":["CAREER 1053605"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1161626"],"award-info":[{"award-number":["CCF-1161626"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["YIP Award N000141110662"],"award-info":[{"award-number":["YIP Award N000141110662"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA9550-12-1-0423"],"award-info":[{"award-number":["FA9550-12-1-0423"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1218620"],"award-info":[{"award-number":["1218620"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00453-016-0145-8","type":"journal-article","created":{"date-parts":[[2016,3,29]],"date-time":"2016-03-29T22:13:19Z","timestamp":1459289599000},"page":"1216-1239","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands"],"prefix":"10.1007","volume":"77","author":[{"given":"Rajesh","family":"Chitnis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hossein","family":"Esfandiari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rohit","family":"Khandekar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saeed","family":"Seddighin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,3,29]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Chekuri, C., Khanna, S., Korula, N.: Approximability of capacitated network design. In: Integer Programming and Combinatoral Optimization-15th International Conference, IPCO 2011, New York, pp. 78\u201391 (2011)","key":"145_CR1","DOI":"10.1007\/978-3-642-20807-2_7"},{"doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Cheung, T.Y., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. J. Algorithms 33(1), 73\u201391 (1999)","key":"145_CR2","DOI":"10.1006\/jagm.1999.1042"},{"issue":"8","key":"145_CR3","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Chitnis, R.H., Esfandiari, H., Hajiaghayi, M., Khandekar, R., Kortsarz, G., Seddighin, S.: A tight algorithm for strongly connected Steiner subgraph on two terminals with demands (extended abstract). In: Parameterized and Exact Computation-9th International Symposium, IPEC 2014, Wroclaw, pp. 159\u2013171 (2014)","key":"145_CR4","DOI":"10.1007\/978-3-319-13524-3_14"},{"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, pp. 1782\u20131801 (2014)","key":"145_CR5","DOI":"10.1137\/1.9781611973402.129"},{"issue":"2","key":"145_CR6","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."},{"unstructured":"Goemans, M.X., Goldberg, A.V., Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9., Williamson, D.P.: Improved approximation algorithms for network design problems. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1994, Arlington, pp. 223\u2013232 (1994)","key":"145_CR7"},{"unstructured":"Guo, C., Lu, G., Li, D., Wu, H., Shi, Y., Zhang, D., Zhang, Y., Lu, S.: Hybrid butterfly cube architecture for modular data centers, US Patent 8,065,433. \n                    https:\/\/www.google.com\/patents\/US8065433\n                    \n                   (2011)","key":"145_CR8"},{"doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC 2003, San Diego, pp. 585\u2013594 (2003)","key":"145_CR9","DOI":"10.1145\/780542.780628"},{"issue":"2","key":"145_CR10","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"unstructured":"Marx, D., Pilipczuk, M.: Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). In: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), Lyon, pp. 542\u2013553 (2014)","key":"145_CR11"},{"doi-asserted-by":"crossref","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. In: Algorithms-ESA 2015-23rd Annual European Symposium, Patras, pp. 865\u2013877 (2015)","key":"145_CR12","DOI":"10.1007\/978-3-662-48350-3_72"},{"doi-asserted-by":"crossref","unstructured":"Marx, D.: A tight lower bound for planar multiway cut with fixed number of terminals. In: Automata, Languages, and Programming-39th International Colloquium, ICALP 2012, Warwick. Part I, pp. 677\u2013688 (2012)","key":"145_CR13","DOI":"10.1007\/978-3-642-31594-7_57"},{"doi-asserted-by":"crossref","unstructured":"Marx, D.: On the optimality of planar and geometric approximation schemes. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), Providence, pp. 338\u2013348 (2007)","key":"145_CR14","DOI":"10.1109\/FOCS.2007.26"},{"unstructured":"Ramachandran, K., Kokku, R., Mahindra, R., Rangarajan, S.: Wireless network connectivity in data centers, US Patent App. 12\/499,906. \n                    http:\/\/www.google.com\/patents\/US20100172292\n                    \n                   (2010)","key":"145_CR15"},{"issue":"4","key":"145_CR16","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1109\/90.532865","volume":"4","author":"S Ramanathan","year":"1996","unstructured":"Ramanathan, S.: Multicast tree generation in networks with asymmetric links. IEEE ACM Trans. Netw. (TON) 4(4), 558\u2013568 (1996)","journal-title":"IEEE ACM Trans. Netw. (TON)"},{"doi-asserted-by":"crossref","unstructured":"Teixeira, R., Marzullo, K., Savage, S., Voelker, G.M.: Characterizing and measuring path diversity of internet topologies. In: International Conference on Measurements and Modeling of Computer Systems, SIGMETRICS 2003, San Diego, pp. 304\u2013305 (2003)","key":"145_CR17","DOI":"10.1145\/781027.781069"},{"doi-asserted-by":"crossref","unstructured":"Teixeira, R., Marzullo, K., Savage, S., Voelker, G.M.: In search of path diversity in ISP networks. In: 3rd ACM SIGCOMM Internet Measurement Conference, IMC 2003, Miami Beach, pp. 313\u2013318 (2003)","key":"145_CR18","DOI":"10.1145\/948205.948247"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0145-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0145-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0145-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0145-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:33:05Z","timestamp":1589697185000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0145-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,29]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["145"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0145-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,3,29]]},"assertion":[{"value":"22 July 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 March 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}