{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:05:02Z","timestamp":1725559502094},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540322122"},{"type":"electronic","value":"9783540322139"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11671541_3","type":"book-chapter","created":{"date-parts":[[2006,1,23]],"date-time":"2006-01-23T12:04:36Z","timestamp":1138017876000},"page":"74-96","source":"Crossref","is-referenced-by-count":1,"title":["Approximation Algorithms for Path Coloring in Trees"],"prefix":"10.1007","author":[{"given":"Ioannis","family":"Caragiannis","sequence":"first","affiliation":[]},{"given":"Christos","family":"Kaklamanis","sequence":"additional","affiliation":[]},{"given":"Giuseppe","family":"Persiano","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"3_CR1","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1145\/235809.235812","volume":"43","author":"A. Aggarwal","year":"1996","unstructured":"Aggarwal, A., Bar-Noy, A., Coppersmith, D., Ramaswami, R., Schieber, B., Sudan, M.: Efficient Routing and Scheduling Algorithms for Optical Networks. Journal of the ACM\u00a043(6), 973\u20131001 (1996)","journal-title":"Journal of the ACM"},{"issue":"1","key":"3_CR2","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/S0304-3975(01)00310-3","volume":"289","author":"V. Auletta","year":"2002","unstructured":"Auletta, V., Caragiannis, I., Kaklamanis, C., Persiano, P.: Randomized Path Coloring on Binary Trees. Theoretical Computer Science\u00a0289(1), 355\u2013399 (2002)","journal-title":"Theoretical Computer Science"},{"key":"3_CR3","unstructured":"Aumann, Y., Rabani, Y.: Improved Bounds for All Optical Routing. In: Proc. of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1995), pp. 567\u2013576 (1995)"},{"issue":"1-2","key":"3_CR4","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/S0304-3975(99)00025-0","volume":"221","author":"Y. Bartal","year":"1999","unstructured":"Bartal, Y., Leonardi, S.: On-Line Routing in All-Optical Networks. Theoretical Computer Science\u00a0221(1-2), 19\u201339 (1999)","journal-title":"Theoretical Computer Science"},{"key":"3_CR5","unstructured":"Beauquier, B., Bermond, J.-C., Gargano, L., Hell, P., Perennes, S., Vaccaro, U.: Graph Problems Arising from Wavelength-Routing in All-Optical Networks. In: 2nd Workshop on Optics and Computer Science (WOCS 1997) (1997)"},{"key":"3_CR6","volume-title":"Graphs and Hypergraphs","author":"C. Berge","year":"1973","unstructured":"Berge, C.: Graphs and Hypergraphs. North-Holland, Amsterdam (1973)"},{"issue":"1-2","key":"3_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0304-3975(98)00018-8","volume":"233","author":"J.-C. Bermond","year":"2000","unstructured":"Bermond, J.-C., Gargano, L., Perennes, S., Rescigno, A.A., Vaccaro, U.: Efficient Collective Communication in Optical Networks. Theoretical Compute Science\u00a0233(1-2), 165\u2013189 (2000)","journal-title":"Theoretical Compute Science"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"732","DOI":"10.1007\/3-540-48224-5_60","volume-title":"Automata, Languages and Programming","author":"I. Caragiannis","year":"2001","unstructured":"Caragiannis, I., Ferreira, A., Kaklamanis, C., Perennes, S., Rivano, H.: Fractional Path Coloring with Applications to WDM Networks. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 732\u2013743. Springer, Heidelberg (2001)"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-540-24749-4_23","volume-title":"STACS 2004","author":"I. Caragiannis","year":"2004","unstructured":"Caragiannis, I., Kaklamanis, C.: Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 258\u2013269. Springer, Heidelberg (2004)"},{"issue":"4","key":"3_CR10","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1142\/S0129626400000299","volume":"10","author":"I. Caragiannis","year":"2000","unstructured":"Caragiannis, I., Kaklamanis, C., Persiano, P.: Symmetric Communication in All-Optical Tree Networks. Parallel Processing Letters\u00a010(4), 305\u2013314 (2000)","journal-title":"Parallel Processing Letters"},{"issue":"1-2","key":"3_CR11","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/S0304-3975(00)00400-X","volume":"270","author":"I. Caragiannis","year":"2002","unstructured":"Caragiannis, I., Kaklamanis, C., Persiano, P.: Edge Coloring of Bipartite Graphs with Constraints. Theoretical Computer Science\u00a0270(1-2), 361\u2013399 (2002)","journal-title":"Theoretical Computer Science"},{"key":"3_CR12","unstructured":"Caragiannis, I., Kaklamanis, C., Persiano, P.: Bounds on Optical Bandwidth Allocation in Directed Fiber Tree Topologies. In: 2nd Workshop on Optics and Computer Science (1997)"},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-540-24592-6_7","volume-title":"Approximation and Online Algorithms","author":"I. Caragiannis","year":"2004","unstructured":"Caragiannis, I., Kaklamanis, C., Persiano, P., Sidiropoulos, A.: Fractional and Integral Coloring of Locally-Symmetric Sets of Paths on Binary Trees. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol.\u00a02909, pp. 81\u201394. Springer, Heidelberg (2004)"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0304-3975(99)00152-8","volume":"255","author":"T. Erlebach","year":"2001","unstructured":"Erlebach, T., Jansen, K.: The Complexity of Path Coloring and Call Scheduling. Theoretical Computer Science\u00a0255, 33\u201350 (2001)","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"3_CR15","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0304-3975(99)00029-8","volume":"221","author":"T. Erlebach","year":"1999","unstructured":"Erlebach, T., Jansen, K., Kaklamanis, C., Mihail, M., Persiano, P.: Optimal Wavelength Routing on Directed Fiber Trees. Theoretical Computer Science\u00a0221(1-2), 119\u2013137 (1999)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"3_CR16","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Garey","year":"1980","unstructured":"Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The Complexity of Coloring Circular Arcs and Chords. SIAM Journal of Algebraic Discrete Methods\u00a01(2), 216\u2013227 (1980)","journal-title":"SIAM Journal of Algebraic Discrete Methods"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/3-540-63165-8_206","volume-title":"Automata, Languages and Programming","author":"L. Gargano","year":"1997","unstructured":"Gargano, L., Hell, P., Perennes, S.: Colouring All Directed Paths in a Symmetric Tree with Applications to WDM Routing. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 505\u2013515. Springer, Heidelberg (1997)"},{"issue":"1","key":"3_CR18","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/0095-8956(85)90088-7","volume":"38","author":"M.C. Golumbic","year":"1985","unstructured":"Golumbic, M.C., Jamison, R.E.: The Edge Intersection Graphs of Paths in a Tree. Journal of Combinatorial Theory Series B\u00a038(1), 8\u201322 (1985)","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"3_CR19","volume-title":"Fiber-Optic Communication Networks","author":"P.E. Green","year":"1992","unstructured":"Green, P.E.: Fiber-Optic Communication Networks. Prentice-Hall, Englewood Cliffs (1992)"},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica\u00a01, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"issue":"4","key":"3_CR21","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Holyer, I.: The NP-Completeness of Edge Coloring. SIAM Journal of Computing\u00a010(4), 718\u2013720 (1981)","journal-title":"SIAM Journal of Computing"},{"key":"3_CR22","unstructured":"Jansen, K.: Approximation Results for Wavelength Routing in Directed Binary Trees. In: 2nd Workshop on Optics and Computer Science (1997)"},{"issue":"1","key":"3_CR23","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01294263","volume":"11","author":"S. Irani","year":"1994","unstructured":"Irani, S.: Coloring Inductive Graphs On-line. Algorithmica\u00a011(1), 53\u201372 (1994)","journal-title":"Algorithmica"},{"issue":"5","key":"3_CR24","first-page":"306","volume":"70","author":"I.A. Karapetian","year":"1980","unstructured":"Karapetian, I.A.: On the Coloring of Circular Arc Graphs. Akad. Nauk Armeyan SSR Doklady\u00a070(5), 306\u2013311 (1980) (in Russian)","journal-title":"Akad. Nauk Armeyan SSR Doklady"},{"key":"3_CR25","unstructured":"Klasing, R.: Methods and Problems of Wavelength-Routing in All-Optical Networks. In: Proc. of MFCS 1998 Workshop on Communication, pp. 1\u20139 (1998)"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Tardos, E.: Disjoint Paths in Densely Embedded Graphs. In: Proc. of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1995), pp. 52\u201361 (1995)","DOI":"10.1109\/SFCS.1995.492462"},{"issue":"3","key":"3_CR27","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1007\/s00453-001-0023-9","volume":"30","author":"V. Kumar","year":"2001","unstructured":"Kumar, V.: An Approximation Algorithm for Circular Arc Coloring. Algorithmica\u00a030(3), 406\u2013417 (2001)","journal-title":"Algorithmica"},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0020-0190(97)00077-X","volume":"62","author":"S.R. Kumar","year":"1997","unstructured":"Kumar, S.R., Panigrahy, R., Russell, A., Sundaram, R.: A Note on Optical Routing in Trees. Information Processing Letters\u00a062, 295\u2013300 (1997)","journal-title":"Information Processing Letters"},{"key":"3_CR29","unstructured":"Kumar, E., Schwabe, E.: Improved Access to Optical Bandwidth in Trees. In: Proc. of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1997), pp. 437\u2013444 (1997)"},{"key":"3_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/3-540-49543-6_19","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"S. Leonardi","year":"1998","unstructured":"Leonardi, S., Vitaletti, A.: Randomized Lower Bounds for On-line Path Coloring. In: Rolim, J.D.P., Serna, M., Luby, M. (eds.) RANDOM 1998. LNCS, vol.\u00a01518, pp. 232\u2013247. Springer, Heidelberg (1998)"},{"key":"3_CR31","unstructured":"Minoli, D.: Telecommunications Technology Handbook, Artech House (1991)"},{"issue":"3","key":"3_CR32","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1137\/0403035","volume":"3","author":"T. Nishizeki","year":"1990","unstructured":"Nishizeki, T., Kashiwagi, K.: On the 1.1 Edge-Coloring of Multigraphs. SIAM Journal of Discrete Mathematics\u00a03(3), 391\u2013410 (1990)","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"3_CR33","unstructured":"Pankaj, R.: Architectures for Linear Lightwave Networks. PhD. Thesis, Department of Electrical Engineering and Computer Science, MIT, Cambridge MA (1992)"},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"Rabani, Y.: Path Coloring on the Mesh. In: Proc. of the 37th IEEE Symposium on Foundations of Computer Science (FOCS 1996), pp. 400\u2013409 (1996)","DOI":"10.1109\/SFCS.1996.548499"},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Raghavan, P., Upfal, E.: Efficient Routing in All-Optical Networks. In: Proc. of the 26th Annual ACM Symposium on the Theory of Computing (STOC 1994), pp. 133\u2013143 (1994)","DOI":"10.1145\/195058.195119"},{"key":"3_CR36","volume-title":"Optical Networks: A Practical Perspective","author":"R. Ramaswami","year":"1998","unstructured":"Ramaswami, R., Sivarajan, K.: Optical Networks: A Practical Perspective. Morgan Kauffman Publishers, San Francisco (1998)"},{"key":"3_CR37","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1002\/sapm1949281148","volume":"28","author":"C.E. Shannon","year":"1949","unstructured":"Shannon, C.E.: A Theorem on Colouring Lines of a Network. J. Math. Phys.\u00a028, 148\u2013151 (1949)","journal-title":"J. Math. Phys."},{"issue":"3","key":"3_CR38","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1137\/0129040","volume":"29","author":"A. Tucker","year":"1975","unstructured":"Tucker, A.: Coloring a Family of Circular Arcs. SIAM Journal on Applied Mathematics\u00a029(3), 493\u2013502 (1975)","journal-title":"SIAM Journal on Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Efficient Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11671541_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:14:29Z","timestamp":1619507669000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11671541_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540322122","9783540322139"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/11671541_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}