{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T06:21:15Z","timestamp":1769062875768,"version":"3.49.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T00:00:00Z","timestamp":1555286400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s00224-019-09922-2","type":"journal-article","created":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T07:02:43Z","timestamp":1555311763000},"page":"1413-1447","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Parameterized Analysis of the Online Priority and Node-Weighted Steiner Tree Problems"],"prefix":"10.1007","volume":"63","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9819-9158","authenticated-orcid":false,"given":"Spyros","family":"Angelopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,15]]},"reference":[{"key":"9922_CR1","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A Agrawal","year":"1995","unstructured":"Agrawal, A., Klein, P.N., Ravi, R.: When trees collide: an approximation algorithm for the generalized steiner tree problem on networks. SIAM J. Comput. 24, 440\u2013456 (1995)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9922_CR2","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1145\/1198513.1198522","volume":"2","author":"N Alon","year":"2006","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: A general approach to online network optimization problems. Trans. Algorithm. 2(4), 640\u2013660 (2006)","journal-title":"Trans. Algorithm."},{"key":"9922_CR3","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF02573969","volume":"10","author":"N Alon","year":"1993","unstructured":"Alon, N., Azar, Y.: On-line Steiner trees in the Euclidean plane. Discret. Comput. Geom. 10, 113\u2013121 (1993)","journal-title":"Discret. Comput. Geom."},{"key":"9922_CR4","unstructured":"Angelopoulos, S.: Improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 248\u2013257 (2007)"},{"key":"9922_CR5","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S.: A near-tight bound for the online steiner tree problem in graphs of bounded asymmetry. In: Proceedings of the 16th Annual European Symposium on Algorithms (ESA), pp. 76\u201387 (2008)","DOI":"10.1007\/978-3-540-87744-8_7"},{"key":"9922_CR6","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S.: Ion the competitiveness of the online asymmetric and euclidean steiner tree problems. In: Proceedings of the 7th International Workshop on Approximation and Online Algorithms (WAOA), pp. 1\u201312 (2009)","DOI":"10.1007\/978-3-642-12450-1_1"},{"issue":"2\u20133","key":"9922_CR7","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.tcs.2004.05.021","volume":"324","author":"B Awerbuch","year":"2004","unstructured":"Awerbuch, B., Azar, Y., Bartal, Y.: On-line generalized Steiner problem. Theor. Comput. Sci. 324(2\u20133), 313\u2013324 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9922_CR8","unstructured":"Basu, P., Chau, C., Gibbens, R.J., Guha, S., Irwin, R.E.: Multicasting under multi-domain and hierarchical constraints. In: 11th International Symposium and Workshops on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, pp. 524\u2013531 (2013)"},{"key":"9922_CR9","doi-asserted-by":"crossref","unstructured":"Berman, P., Coulston, C.: Online algorithms for Steiner tree problems. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, pp. 344\u2013353 (1997)","DOI":"10.1145\/258533.258618"},{"key":"9922_CR10","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M Bern","year":"1989","unstructured":"Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32, 171\u2013176 (1989)","journal-title":"Inf. Process. Lett."},{"key":"9922_CR11","volume-title":"Online computation and competitive analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, Cambridge (1998)"},{"issue":"1","key":"9922_CR12","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/2432622.2432628","volume":"60","author":"J Byrka","year":"2013","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanita\u0307, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6 (2013)","journal-title":"J. ACM"},{"issue":"33","key":"9922_CR13","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"1","author":"M Charikar","year":"1999","unstructured":"Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed steiner problems. J. Algorithm. 1 (33), 73\u201391 (1999)","journal-title":"J. Algorithm."},{"issue":"2","key":"9922_CR14","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1109\/TNET.2004.826288","volume":"12","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Naor, J., Schieber, B.: Resource optimization in QoS multicast routing of real-time multimedia. IEEE\/ACM Trans. Netw. 12(2), 340\u2013348 (2004)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"2","key":"9922_CR15","first-page":"23:1","volume":"4","author":"J Chuzhoy","year":"2008","unstructured":"Chuzhoy, J., Gupta, A., Naor, J., Sinha, A.: On the approximability of some network design problems. Transactions on Algorithms 4(2), 23:1\u201323:17 (2008)","journal-title":"Transactions on Algorithms"},{"key":"9922_CR16","unstructured":"Claffy, K., Polyzos, G., Braun, H.W.: Traffic characteristics of the t1 nsfnet backbone. In: Proceedings of INFOCOM (1993)"},{"key":"9922_CR17","unstructured":"Faloutsos, M.: The Greedy the Naive and the Optimal Multicast Routing\u2013From Theory to Internet Protocols. PhD thesis, University of Toronto (1998)"},{"issue":"6","key":"9922_CR18","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1142\/S0129054102001527","volume":"13","author":"M Faloutsos","year":"2002","unstructured":"Faloutsos, M., Pankaj, R., Sevcik, K. C.: The effect of asymmetry on the on-line multicast routing problem. Int. J. Found. Comput. Sci. 13(6), 889\u2013910 (2002)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"9922_CR19","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 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"9922_CR20","unstructured":"Garg, N., Gupta, A., Leonardi, S., Sankowski, P.: Stochastic analyses for online combinatorial optimization problems. In: Proceedings of the Nineteenth Annual ACM-SIAM, Symposium on Discrete Algorithms, (SODA), pp. 942\u2013951 (2008)"},{"issue":"2","key":"9922_CR21","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM Journal on Computing 24(2), 296\u2013317 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"9922_CR22","doi-asserted-by":"crossref","unstructured":"Gu, A., Gupta, A., Kumar, A.: The power of deferral: maintaining a constant-competitive steiner tree online. In: Proceedings of the 45th Symposium on Theory of Computing Conference (STOC), pp. 525\u2013534 (2013)","DOI":"10.1145\/2488608.2488674"},{"issue":"1","key":"9922_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/140955276","volume":"45","author":"A Gu","year":"2016","unstructured":"Gu, A., Gupta, A., Kumar, A.: The power of deferral: maintaining a constant-competitive steiner tree online. SIAM J. Comput. 45(1), 1\u201328 (2016)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9922_CR24","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1006\/inco.1998.2754","volume":"150","author":"S Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Improved methods for approximating node weighted steiner trees and connected dominating sets. Information and Computation 150(1), 57\u201374 (1999)","journal-title":"Information and Computation"},{"key":"9922_CR25","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A.: Online steiner tree with deletions. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM, Symposium on Discrete Algorithms (SODA), pp. 455\u2013467 (2014)","DOI":"10.1137\/1.9781611973402.34"},{"key":"9922_CR26","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Liaghat, V., Panigrahi, D.: Online node-weighted steiner forest and extensions via disk paintings (2013)","DOI":"10.1109\/FOCS.2013.66"},{"issue":"3","key":"9922_CR27","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M Imase","year":"1991","unstructured":"Imase, M., Waxman, B.: The dynamic Steiner tree problem. SIAM J. Discret. Math. 4(3), 369\u2013384 (1991)","journal-title":"SIAM J. Discret. Math."},{"key":"9922_CR28","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Reducibility among combinatorial problems. In: Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp 85\u2013103. Springer, Boston (1972)"},{"issue":"1","key":"9922_CR29","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P Klein","year":"1995","unstructured":"Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted steiner trees. Journal of Algorithms 19(1), 104\u2013115 (1995)","journal-title":"Journal of Algorithms"},{"key":"9922_CR30","doi-asserted-by":"crossref","unstructured":"Lai, K.J., Gomes, C.P., Schwartz, M.K., McKelvey, Kevin S., Calkin, D.E., Montgomery, C.A.: The steiner multigraph problem: Wildlife corridor design for multiple species. In: Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI) (2011)","DOI":"10.1609\/aaai.v25i1.7809"},{"key":"9922_CR31","doi-asserted-by":"crossref","unstructured":"Naor, J., Panigrahi, D., Singh, M.: Online node-weighted steiner tree and related problems. In: IEEE, 52nd Annual Symposium on Foundations of Computer Science, FOCS, pp. 210\u2013219 (2011)","DOI":"10.1109\/FOCS.2011.65"},{"issue":"8","key":"9922_CR32","doi-asserted-by":"publisher","first-page":"1953","DOI":"10.1016\/j.cor.2003.12.007","volume":"32","author":"CAS Oliveira","year":"2005","unstructured":"Oliveira, C.A.S., Pardalos, P.M.: A survey of combinatorial optimization problems in multicast routing. Comput. Oper Res. 32(8), 1953\u20131981 (2005)","journal-title":"Comput. Oper Res."},{"issue":"4","key":"9922_CR33","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":"9922_CR34","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the twenty-ninth annual ACM Symposium on Theory of Computing, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"issue":"1","key":"9922_CR35","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/S0304-3975(02)00414-0","volume":"295","author":"M Thimm","year":"2003","unstructured":"Thimm, M.: On the approximability of the Steiner tree problem. Theor. Comput. Sci. 295(1), 387\u2013402 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9922_CR36","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proceedings of the thirty-third annual ACM Symposium on Theory of Computing, pp. 453\u2013461 (2001)","DOI":"10.1145\/380752.380839"},{"key":"9922_CR37","volume-title":"Approximation algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation algorithms. Springer, Berlin (2001)"},{"issue":"2","key":"9922_CR38","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0020-0190(95)00000-3","volume":"55","author":"J Westbrook","year":"1995","unstructured":"Westbrook, J., Yan, D.C.K.: Linear bounds for on-line Steiner problems. Inf. Process. Lett. 55(2), 59\u201363 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"9922_CR39","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/BF01185867","volume":"28","author":"J Westbrook","year":"1995","unstructured":"Westbrook, J., Yan, D.C.K.: The performance of greedy algorithms for the on-line Steiner tree and related problems. Math. Syst. Theory 28(5), 451\u2013468 (1995)","journal-title":"Math. Syst. Theory"},{"key":"9922_CR40","unstructured":"Yao, A. C.-C.: Probabilistic computations:towards a unified measure of complexity. In: Proceedings of the 17th Annual IEEE Symposium on Foundations of Computer Science, pp. 222\u2013227 (1997)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09922-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09922-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09922-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T23:27:38Z","timestamp":1663284458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09922-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,15]]},"references-count":40,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["9922"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09922-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,15]]},"assertion":[{"value":"15 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}