{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T04:49:33Z","timestamp":1743050973645,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319135236"},{"type":"electronic","value":"9783319135243"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"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":[[2014]]},"DOI":"10.1007\/978-3-319-13524-3_14","type":"book-chapter","created":{"date-parts":[[2014,12,2]],"date-time":"2014-12-02T17:51:38Z","timestamp":1417542698000},"page":"159-171","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Rajesh Hemant","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":[[2014,12,3]]},"reference":[{"key":"14_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-642-20807-2_7","volume-title":"Integer Programming and Combinatoral Optimization","author":"D Chakrabarty","year":"2011","unstructured":"Chakrabarty, D., Chekuri, C., Khanna, S., Korula, N.: Approximability of Capacitated Network Design. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 78\u201391. Springer, Heidelberg (2011)"},{"issue":"1","key":"14_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M Charikar","year":"1999","unstructured":"Charikar, M., Chekuri, C., Cheung, T.Y., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. J. Algorithm. 33(1), 73\u201391 (1999)","journal-title":"J. Algorithm."},{"issue":"8","key":"14_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."},{"key":"14_CR4","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: SODA, pp. 1782\u20131801 (2014)","DOI":"10.1137\/1.9781611973402.129"},{"issue":"2","key":"14_CR5","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."},{"key":"14_CR6","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: SODA, pp. 223\u2013232 (1994)"},{"key":"14_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 (Nov 22 2011). US patent 8,065,433. http:\/\/www.google.com\/patents\/US8065433"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: STOC \u201903 (2003)","DOI":"10.1145\/780542.780628"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Marx, D.: On optimality of planar & geometric approximation schemes. In: FOCS\u201907 (2007)","DOI":"10.1109\/FOCS.2007.26"},{"key":"14_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/978-3-642-31594-7_57","volume-title":"Automata, Languages, and Programming","author":"D Marx","year":"2012","unstructured":"Marx, D.: A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 677\u2013688. Springer, Heidelberg (2012)"},{"key":"14_CR11","unstructured":"Marx, D., Pilipczuk, M.: Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask). In: STACS, pp. 542\u2013553 (2014)"},{"key":"14_CR12","unstructured":"Ramachandran, K., Kokku, R., Mahindra, R., Rangarajan, S.: Wireless network connectivity in data centers. US patent App. 12\/499, 906. http:\/\/www.google.com\/patents\/US20100172292. Accessed 8 Jul 2010"},{"issue":"4","key":"14_CR13","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. 4(4), 558\u2013568 (1996)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Teixeira, R., Marzullo, K., Savage, S., Voelker, G.M.: Characterizing and measuring path diversity of internet topologies. In: SIGMETRICS, pp. 304\u2013305 (2003)","DOI":"10.1145\/885651.781069"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Teixeira, R., Marzullo, K., Savage, S., Voelker, G.M.: In search of path diversity in ISP networks. In: Internet Measurement Conference, pp. 313\u2013318 (2003)","DOI":"10.1145\/948205.948247"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13524-3_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T01:39:36Z","timestamp":1674178776000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13524-3_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319135236","9783319135243"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13524-3_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"3 December 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}