{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T12:43:09Z","timestamp":1648730589131},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,2,14]],"date-time":"2009-02-14T00:00:00Z","timestamp":1234569600000},"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,10]]},"DOI":"10.1007\/s00453-009-9278-3","type":"journal-article","created":{"date-parts":[[2009,2,16]],"date-time":"2009-02-16T09:54:50Z","timestamp":1234778090000},"page":"516-540","source":"Crossref","is-referenced-by-count":0,"title":["Fractional Path Coloring in Bounded Degree Trees with\u00a0Applications"],"prefix":"10.1007","volume":"58","author":[{"given":"I.","family":"Caragiannis","sequence":"first","affiliation":[]},{"given":"A.","family":"Ferreira","sequence":"additional","affiliation":[]},{"given":"C.","family":"Kaklamanis","sequence":"additional","affiliation":[]},{"given":"S.","family":"P\u00e9rennes","sequence":"additional","affiliation":[]},{"given":"H.","family":"Rivano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,2,14]]},"reference":[{"key":"9278_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/3-540-44436-X_8","volume-title":"APPROX\u201900","author":"V. Auletta","year":"2000","unstructured":"Auletta, V., Caragiannis, I., Kaklamanis, C., Persiano, P.: Randomized path coloring on binary trees. In: APPROX\u201900. Lecture Notes in Computer Science, vol.\u00a01913, pp.\u00a060\u201371. Springer, Berlin (2000)"},{"key":"9278_CR2","doi-asserted-by":"crossref","first-page":"357","DOI":"10.2748\/tmj\/1178243286","volume":"19","author":"K. Azuma","year":"1967","unstructured":"Azuma, K.: Weighted sum of certain dependent random variables. Tohoku Math. J. 19, 357\u2013367 (1967)","journal-title":"Tohoku Math. J."},{"key":"9278_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1007\/3-540-61440-0_160","volume-title":"ICALP\u201996","author":"J.-C. Bermond","year":"1996","unstructured":"Bermond, J.-C., Gargano, L., P\u00e9rennes, S., Rescigno, A.A., Vaccaro, U.: Efficient collective communication in optical networks. In: ICALP\u201996. Lecture Notes in Computer Science, vol.\u00a01099, pp.\u00a0574\u2013585. Springer, Berlin (1996)"},{"key":"9278_CR4","series-title":"Graduate Texts in Mathematics Series","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph Theory","author":"J.A. Bondy","year":"2008","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics Series, vol.\u00a0244. Springer, Berlin (2008)"},{"key":"9278_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/978-3-540-24749-4_23","volume-title":"Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS \u201904)","author":"I. Caragiannis","year":"2004","unstructured":"Caragiannis, I., Kaklamanis, C.: Approximate path coloring with applications to wavelength assignment in WDM optical networks. In: Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS \u201904). Lecture Notes in Computer Science, vol.\u00a02996, pp.\u00a0258\u2013269. Springer, Berlin (2004)"},{"key":"9278_CR6","series-title":"Lecture Notes in Computer Science","first-page":"81","volume-title":"Proceedings of the 1st Workshop on Approximation and On-line Algorithms (WAOA \u201903)","author":"I. Caragiannis","year":"2003","unstructured":"Caragiannis, I., Kaklamanis, C., Persiano, P., Sidiropoulos, A.: Fractional and integral coloring of locally-symmetric sets of paths on binary trees. In: Proceedings of the 1st Workshop on Approximation and On-line Algorithms (WAOA \u201903). Lecture Notes in Computer Science, vol.\u00a02909, pp.\u00a081\u201394. Springer, Berlin (2003)"},{"key":"9278_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/11671541_3","volume-title":"Efficient Approximation and Online Algorithms","author":"I. Caragiannis","year":"2006","unstructured":"Caragiannis, I., Kaklamanis, C., Persiano, P.: Approximation algorithms for path coloring in trees. In: Efficient Approximation and Online Algorithms. Lecture Notes in Computer Science, vol.\u00a03484, pp.\u00a074\u201396. Springer, Berlin (2006)"},{"issue":"7","key":"9278_CR8","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1109\/26.153361","volume":"40","author":"I. Chlamtac","year":"1992","unstructured":"Chlamtac, I., Ganz, A., Karmi, G.: Lightpath communications: An approach to high bandwidth optical WAN\u2019s. IEEE Trans. Commun. 40(7), 1171\u20131182 (1992)","journal-title":"IEEE Trans. Commun."},{"issue":"1\u20132","key":"9278_CR9","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 221(1\u20132), 119\u2013137 (1999)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9278_CR10","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J.\u00a0Comput. Syst. Sci. 57(2), 187\u2013199 (1998)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9278_CR11","unstructured":"Ferreira, A., P\u00e9rennes, S., Richa, A., Rivano, H., Stier, N.: On the design of multifiber WDM networks. In: AlgoTel\u201902, M\u00e8ze, France, May 2002, pp.\u00a025\u201332"},{"key":"9278_CR12","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9278_CR13","unstructured":"Garg, N.: Multicommodity flows and approximation algorithms. Ph.D. thesis, Indian Institute of Technology, Delhi, April (1994)"},{"issue":"1","key":"9278_CR14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"key":"9278_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/3-540-63165-8_206","volume-title":"ICALP\u201997","author":"L. Gargano","year":"1997","unstructured":"Gargano, L., Hell, P., P\u00e9rennes, S.: Colouring paths in directed symmetric trees with applications to WDM routing. In: ICALP\u201997. Lecture Notes in Computer Science, vol.\u00a01256, pp.\u00a0505\u2013515. Springer, Berlin (1997)"},{"key":"9278_CR16","doi-asserted-by":"crossref","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. J.\u00a0Comb. Theory 38, 8\u201322 (1985)","journal-title":"J.\u00a0Comb. Theory"},{"key":"9278_CR17","doi-asserted-by":"crossref","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 1, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"9278_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, vol.\u00a02, 2nd corrected edn. Springer, Berlin (1993)","edition":"2"},{"key":"9278_CR19","volume-title":"Approximation Algorithms for NP-Hard Problems","year":"1997","unstructured":"Hochbaum, D.S. (ed.): Approximation Algorithms for NP-Hard Problems. PWS-Kent, Boston (1997)"},{"key":"9278_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1007\/3-540-45841-7_7","volume-title":"Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS \u201902)","author":"K. Jansen","year":"2002","unstructured":"Jansen, K.: Approximate strong separation with application in fractional graph coloring and preemptive scheduling. In: Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS \u201902). Lecture Notes in Computer Science, vol.\u00a02285, pp.\u00a0100\u2013111. Springer, Berlin (2002)"},{"issue":"5","key":"9278_CR21","first-page":"306","volume":"70","author":"I.A. Karapetyan","year":"1980","unstructured":"Karapetyan, I.A.: On coloring of arc graphs. Dokl. Akad. Nauk Armianskoi CCP 70(5), 306\u2013311 (1980). In Russian","journal-title":"Dokl. Akad. Nauk Armianskoi CCP"},{"key":"9278_CR22","unstructured":"K\u00f6nig, D.: Graphok \u00e9s matrixok. Mat. Fiz. Lapok 116\u2013119 (1931)"},{"key":"9278_CR23","doi-asserted-by":"crossref","unstructured":"Kumar, V.: Approximating arc circular colouring and bandwidth allocation in all-optical ring networks. In: APPROX\u201998 (1998)","DOI":"10.1007\/BFb0053971"},{"key":"9278_CR24","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13, 383\u2013390 (1975)","journal-title":"Discrete Math."},{"key":"9278_CR25","unstructured":"Niessen, T., Kind, J.: The round-up property of the fractional chromatic number for proper circular arc graphs, J.\u00a0Graph Theory (1998)"},{"issue":"2","key":"9278_CR26","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55(2), 221\u2013232 (1985)","journal-title":"Discrete Math."},{"issue":"3","key":"9278_CR27","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1137\/0129040","volume":"29","author":"A. Tucker","year":"1975","unstructured":"Tucker, A.: Coloring a family of circular arcs. SIAM J. Appl. Math. 29(3), 493\u2013502 (1975)","journal-title":"SIAM J. Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9278-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9278-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9278-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:03Z","timestamp":1559137503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9278-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,14]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["9278"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9278-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2,14]]}}}