{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T21:06:50Z","timestamp":1672348010440},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2006,3]]},"DOI":"10.1007\/s10878-006-7135-8","type":"journal-article","created":{"date-parts":[[2006,5,4]],"date-time":"2006-05-04T16:10:21Z","timestamp":1146759021000},"page":"219-229","source":"Crossref","is-referenced-by-count":6,"title":["Inapproximability and approximability of maximal tree routing and coloring"],"prefix":"10.1007","volume":"11","author":[{"given":"Xujin","family":"Chen","sequence":"first","affiliation":[]},{"given":"Xiaodong","family":"Hu","sequence":"additional","affiliation":[]},{"given":"Tianping","family":"Shuai","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7135_CR1","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M Bellare","year":"1998","unstructured":"Bellare M, Goldreich O, Sudan M (1998) Free bits and nonapproximability\u2013towards tight results, SIAM Journal on Computing 27:804\u2013915","journal-title":"SIAM Journal on Computing"},{"key":"7135_CR2","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/11496199_3","volume":"3521","author":"X-J Chen","year":"2005","unstructured":"Chen X-J, Hu X-D, Jia X-H (2005) Complexity of minimal tree routing and coloring, Lecture Notes in Computer Science 3521:6\u201315","journal-title":"Lecture Notes in Computer Science"},{"key":"7135_CR3","unstructured":"Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman and Company"},{"key":"7135_CR4","doi-asserted-by":"crossref","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 (2004) Routing algorithm for multicast under multi-tree model in optical networks, Theoretical Computer Science 314:293\u2013301","journal-title":"Theoretical Computer Science"},{"key":"7135_CR5","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"UI Gupta","year":"1982","unstructured":"Gupta UI, Lee DT, Leung Y-T (1982) Efficient algorithms for interval graphs and circular-arc graphs, Networks 12:459\u2013467","journal-title":"Networks"},{"key":"7135_CR6","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","volume":"10","author":"P Hall","year":"1935","unstructured":"Hall P (1935) On representatives of subsets, Journal of the London Mathematical Society 10:26\u201330","journal-title":"Journal of the London Mathematical Society"},{"key":"7135_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00020","volume":"4","author":"MM Halld\u00f3rsson","year":"2000","unstructured":"Halld\u00f3rsson MM (2000) Approximations of weighted independent set and hereditary subset problems, Journal of Graph Algorithms and Applications 4:1\u201316","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"7135_CR8","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J Hastad","year":"1999","unstructured":"Hastad J (1999) Clique is hard to approximate within $$n^1-\\epsilon$$ , Acta Mathematica 182:105\u2013142","journal-title":"Acta Mathematica"},{"key":"7135_CR9","doi-asserted-by":"crossref","unstructured":"Kleinberg J, Tardos E (1995) Disjoint paths in densely embedded graphs, in Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, Santa Fe, New Mexico, 52\u201361","DOI":"10.1109\/SFCS.1995.492462"},{"key":"7135_CR10","doi-asserted-by":"crossref","unstructured":"Kollipoulos SG, Stein C (1998) Approximating disjoint-path problems using greedy algorithms and packing integer programs, Integer Programming and Combinatorial Optimization, Houston, TX","DOI":"10.1007\/3-540-69346-7_12"},{"key":"7135_CR11","unstructured":"Kramer ME, van Leeuwen J The complexity of wire routing and finding the minimum area layouts for arbitrary VLSI circuits, in F.P. Preparata, editor, Advances in Computing Research; VLSI Theory 2:129\u2013146, JAI Press Inc. Greenwich, CT-London"},{"key":"7135_CR12","unstructured":"Nomikos C (2000) Routing and path coloring in rings: NP-completeness, Technical Report 15-2000, University of loannina, Greece"},{"key":"7135_CR13","doi-asserted-by":"crossref","unstructured":"Nomikos C, Pagourtzis A, Zachos S (2003) Minimizing request blocking in all-optical rings, in Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA","DOI":"10.1109\/INFCOM.2003.1208971"},{"key":"7135_CR14","unstructured":"Nomikos C, Zachos S (1997) Coloring a maximum number of paths in graphs, in Workshop on Algorithmic Aspects of Communication, Bologna"},{"key":"7135_CR15","unstructured":"Robins G, Zelikovsky A (2000) Improved Steiner tree approximation in graphs, in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, California, United States, pp. 770\u2013779"},{"key":"7135_CR16","doi-asserted-by":"crossref","unstructured":"Wan PJ, Liu L (1998) Maximal throughput in wavelength-routed optical networks, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 46:15\u201326","DOI":"10.1090\/dimacs\/046\/02"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-7135-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-006-7135-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-7135-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:09Z","timestamp":1559261889000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-006-7135-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["7135"],"URL":"https:\/\/doi.org\/10.1007\/s10878-006-7135-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3]]}}}