{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T14:15:43Z","timestamp":1761401743170,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319126906"},{"type":"electronic","value":"9783319126913"}],"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-12691-3_16","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T21:11:32Z","timestamp":1415999492000},"page":"200-215","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Practical Greedy Approximation for the Directed Steiner Tree Problem"],"prefix":"10.1007","author":[{"given":"Dimitri","family":"Watel","sequence":"first","affiliation":[]},{"given":"Marc-Antoine","family":"Weisser","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,13]]},"reference":[{"key":"16_CR1","volume-title":"Reducibility Among Combinatorial Problems","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility Among Combinatorial Problems. Springer, New York (1972)"},{"issue":"2","key":"16_CR2","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"L Kou","year":"1981","unstructured":"Kou, L., Markowsky, G., Berman, L.: A fast algorithm for steiner trees. Acta Inf. 15(2), 141\u2013145 (1981)","journal-title":"Acta Inf."},{"issue":"5","key":"16_CR3","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"AZ Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.Z.: An 11\/6-approximation algorithm for the network steiner problem. Algorithmica 9(5), 463\u2013470 (1993)","journal-title":"Algorithmica"},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/2432622.2432628","volume":"60","author":"J Byrka","year":"2013","unstructured":"Byrka, J., Grandoni, F., Rothvoss, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM (JACM) 60(1), 6:1\u20136:33 (2013)","journal-title":"J. ACM (JACM)"},{"key":"16_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0255-1","volume-title":"Steiner Trees in Industry","author":"X Cheng","year":"2001","unstructured":"Cheng, X., Du, D.Z.: Steiner Trees in Industry, vol. 11. Springer, New York (2001)"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/978-0-387-30165-5_18","volume-title":"Handbook of Optimization in Telecommunications","author":"S Vo\u00df","year":"2006","unstructured":"Vo\u00df, S.: Steiner tree problems in telecommunications. In: Resende, M.G.C., Pardalos, P.M. (eds.) Handbook of Optimization in Telecommunications, pp. 459\u2013492. Springer, New York (2006)"},{"issue":"12","key":"16_CR7","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1016\/S0305-0548(00)00029-0","volume":"28","author":"R Novak","year":"2001","unstructured":"Novak, R., Rugelj, J., Kandus, G.: A note on distributed multicast routing in point-to-point networks. Comput. Oper. Res. 28(12), 1149\u20131164 (2001)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"16_CR8","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM (JACM) 45(4), 634\u2013652 (1998)","journal-title":"J. ACM (JACM)"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 585\u2013594 (2003)","DOI":"10.1145\/780542.780628"},{"issue":"1","key":"16_CR10","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., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed steiner problems. J. Algorithms 33(1), 73\u201391 (1999)","journal-title":"J. Algorithms"},{"issue":"1","key":"16_CR11","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":"16_CR12","doi-asserted-by":"crossref","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. In: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, pp. 38\u201349 (1973)","DOI":"10.1145\/800125.804034"},{"issue":"3","key":"16_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Olsson, P.M., Kvarnstrom, J., Doherty, P., Burdakov, O., Holmberg, K.: Generating uav communication networks for monitoring and surveillance. In: 2010 11th International Conference on Control Automation Robotics & Vision (ICARCV), pp. 1070\u20131077. IEEE (2010)","DOI":"10.1109\/ICARCV.2010.5707968"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Gundecha, P., Feng, Z., Liu, H.: Seeking provenance of information using social media. In: Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, pp. 1691\u20131696. ACM (2013)","DOI":"10.1145\/2505515.2505633"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Lappas, T., Terzi, E., Gunopulos, D., Mannila, H.: Finding effectors in social networks. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1059\u20131068. ACM (2010)","DOI":"10.1145\/1835804.1835937"},{"key":"16_CR17","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-1-4613-0255-1_9","volume-title":"Steiner Trees in Industry","author":"T Koch","year":"2001","unstructured":"Koch, T., Martin, A., Vo\u00df, S.: SteinLib: an updated library on Steiner tree problems in graphs. In: Cheng, X.Z., Du, D.-Z. (eds.) Steiner Trees in Industry, pp. 285\u2013325. Springer, New York (2001)"},{"key":"16_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-25591-5_6","volume-title":"Algorithms and Computation","author":"M Chimani","year":"2011","unstructured":"Chimani, M., Woste, M.: Contraction-based steiner tree approximations in practice. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 40\u201349. Springer, Heidelberg (2011)"},{"issue":"1","key":"16_CR19","doi-asserted-by":"crossref","first-page":"41","DOI":"10.15837\/ijccc.2006.1.2271","volume":"1","author":"M Stanojevic","year":"2006","unstructured":"Stanojevic, M., Vujosevic, M.: An exact algorithm for steiner tree problem on graphs. Int. J. Comput. Commun. Control 1(1), 41\u201346 (2006)","journal-title":"Int. J. Comput. Commun. Control"},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"Uchoa, E., Werneck, R.F.F.: Fast local search for steiner trees in graphs. In: ALENEX, vol. 10, pp. 1\u201310. SIAM (2010)","DOI":"10.1137\/1.9781611972900.1"},{"issue":"2","key":"16_CR21","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1002\/net.20276","volume":"53","author":"L Drummond","year":"2009","unstructured":"Drummond, L., Santos, M., Uchoa, E.: A distributed dual ascent algorithm for steiner problems in multicast routing. Networks 53(2), 170\u2013183 (2009)","journal-title":"Networks"},{"key":"16_CR22","first-page":"1409","volume":"22","author":"MI Hsieh","year":"2006","unstructured":"Hsieh, M.I., Wu, E.H.K., Tsai, M.F.: Fasterdsp: a faster approximation algorithm for directed steiner tree problem. J. Inf. Sci. Eng. 22, 1409\u20131425 (2006)","journal-title":"J. Inf. Sci. Eng."},{"key":"16_CR23","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/S1571-0653(04)00247-1","volume":"7","author":"MP de Arag\u00e3o","year":"2001","unstructured":"de Arag\u00e3o, M.P., Uchoa, E., Werneck, R.F.: Dual heuristics on the exact solution of large steiner problems. Electron. Notes Discrete Math. 7, 150\u2013153 (2001)","journal-title":"Electron. Notes Discrete Math."},{"issue":"3","key":"16_CR24","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/BF02612335","volume":"28","author":"RT Wong","year":"1984","unstructured":"Wong, R.T.: A dual ascent approach for steiner tree problems on a directed graph. Math. Program. 28(3), 271\u2013287 (1984)","journal-title":"Math. Program."},{"issue":"7","key":"16_CR25","doi-asserted-by":"publisher","first-page":"2147","DOI":"10.1016\/j.cor.2005.08.009","volume":"34","author":"V Melkonian","year":"2007","unstructured":"Melkonian, V.: New primal-dual algorithms for steiner tree problems. Comput. Oper. Res. 34(7), 2147\u20132167 (2007)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"16_CR26","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","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12691-3_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T14:26:49Z","timestamp":1675348009000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-12691-3_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319126906","9783319126913"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12691-3_16","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":"13 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}