{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:57Z","timestamp":1725490257804},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_31","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:32:38Z","timestamp":1188351158000},"page":"351-362","source":"Crossref","is-referenced-by-count":12,"title":["Approximation Algorithms and Complexity Results for Path Problems in Trees of Rings"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Erlebach","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"B. Beauquier, S. P\u00e9rennes, and D. T\u00f3th. All-to-all routing and coloring in weighted trees of rings. In Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures SPAA\u2019 99, pages 185\u2013190, 1999.","key":"31_CR1","DOI":"10.1145\/305619.305639"},{"issue":"3","key":"31_CR2","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/A:1009822211065","volume":"4","author":"P. Berman","year":"2000","unstructured":"P. Berman and B. DasGupta. Multi-phase algorithms for throughput maximization for real-time scheduling. Journal of Combinatorial Optimization, 4(3):307\u2013323, 2000.","journal-title":"Journal of Combinatorial Optimization"},{"key":"31_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1007\/3-540-40996-3_13","volume-title":"Proceedings of the 11th Annual International Symposium on Algorithms and Computation ISAAC 2000","author":"X. Deng","year":"2000","unstructured":"X. Deng, G. Li, W. Zang, and Y. Zhou. A 2-approximation algorithm for path coloring on trees of rings. In Proceedings of the 11th Annual International Symposium on Algorithms and Computation ISAAC 2000, LNCS 1969, pages 144\u2013155, 2000."},{"doi-asserted-by":"crossref","unstructured":"T. Erlebach. Approximation algorithms and complexity results for path problems in trees of rings. TIK-Report 109, Computer Engineering and Networks Laboratory (TIK), ETH Z\u00fcrich, June 2001. Available electronically at ftp:\/\/ftp.tik.ee.ethz.ch\/pub\/publications\/TIK-Report109.pdf .","key":"31_CR4","DOI":"10.1007\/3-540-44683-4_31"},{"key":"31_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/3-540-49381-6_20","volume-title":"Proceedings of the 9th Annual International Symposium on Algorithms and Computation ISAAC\u201998","author":"T. Erlebach","year":"1998","unstructured":"T. Erlebach and K. Jansen. Maximizing the number of connections in optical tree networks. In Proceedings of the 9th Annual International Symposium on Algorithms and Computation ISAAC\u201998, LNCS 1533, pages 179\u2013188, 1998."},{"key":"31_CR6","first-page":"135","volume":"8","author":"T. Erlebach","year":"2000","unstructured":"T. Erlebach and K. Jansen. Conversion of coloring algorithms into maximum weight independent set algorithms. In ICALP Workshops 2000, Proceedings in Informatics 8, pages 135\u2013145. Carleton Scientific, 2000.","journal-title":"ICALP Workshops 2000, Proceedings in Informatics"},{"issue":"1\u20132","key":"31_CR7","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0304-3975(99)00152-8","volume":"255","author":"T. Erlebach","year":"2001","unstructured":"T. Erlebach and K. Jansen. The complexity of path coloring and call scheduling. Theoretical Computer Science, 255(1\u20132):33\u201350, 2001.","journal-title":"Theoretical Computer Science"},{"key":"31_CR8","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0304-3975(99)00029-8","volume":"221","author":"T. Erlebach","year":"1999","unstructured":"T. Erlebach, K. Jansen, C. Kaklamanis, M. Mihail, and P. Persiano. Optimal wavelength routing on directed fiber trees. Theoretical Computer Science, 221:119\u2013137, 1999. Special issue of ICALP\u201997.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"31_CR9","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M. R. Garey","year":"1980","unstructured":"M. R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitriou. The complexity of coloring circular arcs and chords. SIAM J. Algebraic Discrete Methods, 1(2):216\u2013227, 1980.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"31_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"N. Garg, V. V. Vazirani, and M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18:3\u201320, 1997.","journal-title":"Algorithmica"},{"unstructured":"J. Kleinberg. Approximation algorithms for disjoint paths problems. PhD thesis, MIT, 1996.","key":"31_CR11"},{"key":"31_CR12","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0020-0190(97)00077-X","volume":"62","author":"S. R. Kumar","year":"1997","unstructured":"S. R. Kumar, R. Panigrahy, A. Russel, and R. Sundaram. A note on optical routing on trees. Inf. Process. Lett., 62:295\u2013300, 1997.","journal-title":"Inf. Process. Lett."},{"unstructured":"M. Mihail, C. Kaklamanis, and S. Rao. Efficient access to optical bandwidth. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science FOCS\u201995, pages 548\u2013557, 1995.","key":"31_CR13"},{"doi-asserted-by":"crossref","unstructured":"P. Raghavan and E. Upfal. Efficient routing in all-optical networks. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing STOC\u201994, pages 134\u2013143, 1994.","key":"31_CR14","DOI":"10.1145\/195058.195119"},{"doi-asserted-by":"crossref","unstructured":"P.-J. Wan and L. Liu. Maximal throughput in wavelength-routed optical networks. In Multichannel Optical Networks: Theory and Practice, volume 46 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 15\u201326. AMS, 1998.","key":"31_CR15","DOI":"10.1090\/dimacs\/046\/02"},{"unstructured":"G. Wilfong and P. Winkler. Ring routing and wavelength translation. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms SODA\u201998, pages 333\u2013341, 1998.","key":"31_CR16"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T23:09:28Z","timestamp":1684019368000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_31","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}