{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:37Z","timestamp":1725558997162},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540262244"},{"type":"electronic","value":"9783540324409"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11496199_3","type":"book-chapter","created":{"date-parts":[[2010,7,14]],"date-time":"2010-07-14T10:29:15Z","timestamp":1279103355000},"page":"6-15","source":"Crossref","is-referenced-by-count":1,"title":["Complexity of Minimal Tree Routing and Coloring"],"prefix":"10.1007","author":[{"given":"Xujin","family":"Chen","sequence":"first","affiliation":[]},{"given":"Xiaodong","family":"Hu","sequence":"additional","affiliation":[]},{"given":"Xiaohua","family":"Jia","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits and non-approximability-towards tight results. SIAM Journal on Computing\u00a027, 804\u2013915 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR2","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"},{"key":"3_CR3","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a057, 187\u2013199 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, New York (1979)"},{"key":"3_CR5","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, Ser. B\u00a038, 8\u201322 (1985)","journal-title":"Journal of Combinatorial Theory, Ser. B"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.tcs.2003.12.019","volume":"314","author":"J. Gu","year":"2004","unstructured":"Gu, J., Hu, X.-D., Jia, X.-H., Zhang, M.-H.: Routing algorithm for multicast under multi-tree model in optical networks. Theoretical Computer Science\u00a0314, 293\u2013301 (2004)","journal-title":"Theoretical Computer Science"},{"key":"3_CR7","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-540-24596-4_10","volume-title":"High Performance Computing - HiPC 2003","author":"Q. Gu","year":"2003","unstructured":"Gu, Q., Wang, Y.: Efficient algorithm for embedding hypergraphs in a cycle. In: Pinkston, T.M., Prasanna, V.K. (eds.) HiPC 2003. LNCS (LNAI), vol.\u00a02913, pp. 85\u201394. Springer, Heidelberg (2003)"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"U.I. Gupta","year":"1982","unstructured":"Gupta, U.I., Lee, D.T., Leung, Y.-T.: Efficient algorithms for interval graphs and circular-arc graphs. Networks\u00a012, 459\u2013467 (1982)","journal-title":"Networks"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: A still better performance guarantee for approximate graph coloring. Information Processing Letters\u00a045, 19\u201323 (1993)","journal-title":"Information Processing Letters"},{"key":"3_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/3-540-69346-7_12","volume-title":"Integer Programming and Combinatorial Optimization","author":"S.G. Kollipoulos","year":"1998","unstructured":"Kollipoulos, S.G., Stein, C.: Approximating disjoint-path problems using greedy algorithms and packing integer programs. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol.\u00a01412, p. 153. Springer, Heidelberg (1998)"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"L. Kou","year":"1981","unstructured":"Kou, L., Markowsky, G., Berman, L.: A fast algorithm for steiner trees. Acta Informatica\u00a015, 141\u2013145 (1981)","journal-title":"Acta Informatica"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"36","author":"C.S..J.A. Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.S.J.A.: Edge disjoint spanning trees of finite graphs. Journal of London Mathematical Society\u00a036, 445\u2013450 (1961)","journal-title":"Journal of London Mathematical Society"},{"key":"3_CR13","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 on Discrete Mathematics\u00a03, 391\u2013410 (1990)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"3_CR14","unstructured":"Nomikos, C.: Path coloring in graphs, Ph.D Thesis, Department of Electrical and Computer Engineering, NTUA (1997)"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Rabani, Y.: Path coloring on the mesh. In: Proceedings of the 37th Annual Symposium Foundations of Computer Science, pp. 400\u2013409 (1996)","DOI":"10.1109\/SFCS.1996.548499"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Raghavan, P., Upfal, E.: Efficient routing in all-optical networks. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pp. 134\u2013143 (1994)","DOI":"10.1145\/195058.195119"},{"issue":"2","key":"3_CR17","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1109\/35.747251","volume":"37","author":"L.H. Sahasrabuddhe","year":"1999","unstructured":"Sahasrabuddhe, L.H., Mukherjee, B.: Light-trees: optical multicasting for improved performance in wavelength-routed networks. IEEE Communications Magazine\u00a037(2), 67\u201373 (1999)","journal-title":"IEEE Communications Magazine"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"R. Tarjan","year":"1985","unstructured":"Tarjan, R.: Decomposition by clique separators. Discrete Mathematics\u00a055, 221\u2013232 (1985)","journal-title":"Discrete Mathematics"},{"key":"3_CR19","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, 493\u2013502 (1975)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1112\/jlms\/s1-36.1.221","volume":"36","author":"W.T. Tutte","year":"1961","unstructured":"Tutte, W.T.: On the problem of decomposing a graph into n connected factors. Journal of London Mathematical Society\u00a036, 221\u2013230 (1961)","journal-title":"Journal of London Mathematical Society"},{"key":"3_CR21","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1090\/dimacs\/046\/02","volume":"46","author":"P.J. Wan","year":"1998","unstructured":"Wan, P.J., Liu, L.: Maximal throughput in wavelength-routed optical networks. DIMACS Series in Discrete Mathematics and Theoretical Computer Science\u00a046, 15\u201326 (1998)","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Applications in Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11496199_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:39:56Z","timestamp":1619505596000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11496199_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540262244","9783540324409"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11496199_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}