{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T22:40:01Z","timestamp":1739054401288,"version":"3.37.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,4,8]],"date-time":"2009-04-08T00:00:00Z","timestamp":1239148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,7]]},"DOI":"10.1007\/s00453-009-9305-4","type":"journal-article","created":{"date-parts":[[2009,4,7]],"date-time":"2009-04-07T17:53:56Z","timestamp":1239126836000},"page":"517-537","source":"Crossref","is-referenced-by-count":1,"title":["A Preemptive Algorithm for Maximizing Disjoint Paths on Trees"],"prefix":"10.1007","volume":"57","author":[{"given":"Yossi","family":"Azar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uriel","family":"Feige","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Glasner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,4,8]]},"reference":[{"key":"9305_CR1","unstructured":"Adler, R., Azar, Y.: Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms. In: Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a01\u201310 (1999)"},{"key":"9305_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Arad, U., Azar, Y.: Independent sets in hypergraphs with applications to routing via fixed paths. In: Proc. 2nd Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 16\u201327 (1999)","DOI":"10.1007\/978-3-540-48413-4_3"},{"key":"9305_CR3","doi-asserted-by":"crossref","unstructured":"Andrews, M., Chuzhoy, J., Khanna, S., Zhang, L.: Hardness of the undirected edge-disjoint paths problem with congestion. In: Proceedings 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 226\u2013244 (2005)","DOI":"10.1109\/SFCS.2005.41"},{"issue":"3","key":"9305_CR4","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J. Aspnes","year":"1997","unstructured":"Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM 44(3), 486\u2013504 (1997). Also in Proc. 25th ACM STOC, 1993, pp. 623\u2013631","journal-title":"J. ACM"},{"key":"9305_CR5","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Plotkin, S.: Throughput-competitive online routing. In: 34th IEEE Symposium on Foundations of Computer Science, pp. 32\u201340 (1993)","DOI":"10.1109\/SFCS.1993.366884"},{"key":"9305_CR6","unstructured":"Awerbuch, B., Bartal, Y., Fiat, A., Ros\u00e9n, A.: Competitive non-preemptive call control. In: Proc. of 5th ACM-SIAM Symposium on Discrete Algorithms, pp. 312\u2013320 (1994)"},{"key":"9305_CR7","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Gawlick, R., Leighton, T., Rabani, Y.: On-line admission control and circuit routing for high performance computation and communication. In: Proc. 35th IEEE Symp. on Found. of Comp. Science, pp. 412\u2013423 (1994)","DOI":"10.1109\/SFCS.1994.365675"},{"key":"9305_CR8","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Fiat, A., Leonardi, S., Rosen, A.: On-line competitive algorithms for call admission in optical networks. In: Proc. 4th Annual European Symposium on Algorithms, pp. 431\u2013444 (1996)","DOI":"10.1007\/3-540-61680-2_73"},{"key":"9305_CR9","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Fiat, A., Leonardi, S.: Lower bounds for on-line graph problems with application to on-line circuit and optical routing. In: Proc. 28th ACM Symp. on Theory of Computing, pp. 531\u2013540 (1996)","DOI":"10.1145\/237814.238001"},{"key":"9305_CR10","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)"},{"key":"9305_CR11","volume-title":"Introduction to Algorithms","author":"T.T. Cormen","year":"1990","unstructured":"Cormen, T.T., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge (1990)"},{"key":"9305_CR12","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1006\/jagm.1996.0821","volume":"23","author":"J. Garay","year":"1997","unstructured":"Garay, J., Gopal, I., Kutten, S., Mansour, Y., Yung, M.: Efficient on-line call control algorithms. J.\u00a0Algorithms 23, 180\u2013194 (1997). Also in Proc. 2nd Annual Israel Conference on Theory of Computing and Systems (1993)","journal-title":"J.\u00a0Algorithms"},{"key":"9305_CR13","doi-asserted-by":"crossref","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. In: ALGORITHMICA, vol. 18, pp. 3\u201320 (1997)","DOI":"10.1007\/BF02523685"},{"key":"9305_CR14","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Tardos, E.: Disjoint paths in densely embedded graphs. In: Proc. 36th IEEE Symp. on Found. of Comp. Science, pp. 52\u201361 (1995)","DOI":"10.1109\/SFCS.1995.492462"},{"key":"9305_CR15","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1007\/BFb0029572","volume-title":"Online Algorithms\u2014The State of the Art","author":"S. Leonardi","year":"1998","unstructured":"Leonardi, S.: On-line network routing. In: Fiat, A., Woeginger, G. (eds.) Online Algorithms\u2014The State of the Art, pp. 242\u2013267. Springer, Berlin (1998). Chap. 11"},{"key":"9305_CR16","unstructured":"Leonardi, S., Marchetti-Spaccamela, A., Presciutti, A., Ros\u00e9n, A.: On-line randomized call control revisited. In: Proc. 9th ACM-SIAM Symp. on Discrete Algorithms, pp. 323\u2013332 (1998)"},{"key":"9305_CR17","unstructured":"Lipton, R.J., Tomkins, A.: Online interval scheduling. In: Proc. of the 5th ACM-SIAM Symposium on Discrete Algorithms, pp. 302\u2013311 (1994)"},{"issue":"4","key":"9305_CR18","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365\u2013374 (1987)","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9305-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9305-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9305-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T22:01:13Z","timestamp":1739052073000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9305-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,8]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["9305"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9305-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2009,4,8]]}}}