{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T11:32:22Z","timestamp":1648899142130},"reference-count":20,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2002,11,1]],"date-time":"2002-11-01T00:00:00Z","timestamp":1036108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Algorithms"],"published-print":{"date-parts":[[2002,11]]},"DOI":"10.1016\/s0196-6774(02)00214-6","type":"journal-article","created":{"date-parts":[[2002,12,10]],"date-time":"2002-12-10T18:17:21Z","timestamp":1039544241000},"page":"93-125","source":"Crossref","is-referenced-by-count":8,"title":["Wavelength rerouting in optical networks, or the Venetian Routing problem"],"prefix":"10.1016","volume":"45","author":[{"given":"Alberto","family":"Caprara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Mohan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0196-6774(02)00214-6_BIB001","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1006\/jcss.1997.1472","article-title":"The hardness of approximate optima in lattices, codes, and systems of linear equations","volume":"54","author":"Arora","year":"1997","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0196-6774(02)00214-6_BIB002","series-title":"Proc. IEEE Symposium on Foundations of Computer Science","first-page":"276","article-title":"Randomness-efficient oblivious sampling","author":"Bellare","year":"1994"},{"key":"10.1016\/S0196-6774(02)00214-6_BIB003","series-title":"Proc. ACM\u2013SIAM Symposium on Discrete Algorithms","first-page":"345","article-title":"On the red\u2013blue set cover problem","author":"Carr","year":"2000"},{"key":"10.1016\/S0196-6774(02)00214-6_BIB004","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1109\/26.153361","article-title":"Lightpath communications: An approach to high bandwidth optical WANs","volume":"40","author":"Chlamtac","year":"1992","journal-title":"IEEE Trans. Commun."},{"key":"10.1016\/S0196-6774(02)00214-6_BIB005","series-title":"Proc. 4th Israel Symposium on Theory of Computing and Systems","first-page":"68","article-title":"To weight or not to weight: Where is the question?","author":"Crescenzi","year":"1996"},{"key":"10.1016\/S0196-6774(02)00214-6_BIB006","series-title":"Proc. ACM Symposium on Theory of Computing","first-page":"750","article-title":"Designing networks with bounded pairwise distance","author":"Dodis","year":"1999"},{"key":"10.1016\/S0196-6774(02)00214-6_BIB007","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W","article-title":"Efficient approximations for product distributions","volume":"13","author":"Even","year":"1998","journal-title":"Random Structures Algorithms"},{"key":"10.1016\/S0196-6774(02)00214-6_BIB008","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1006\/jcss.1998.1587","article-title":"Zero knowledge and the chromatic number","volume":"57","author":"Feige","year":"1998","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0196-6774(02)00214-6_BIB009","series-title":"Computers and Intractability","author":"Garey","year":"1979"},{"key":"10.1016\/S0196-6774(02)00214-6_BIB010","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Clique is hard to approximate within n1\u2212\u03b5, Acta Math., to appear","DOI":"10.1007\/BF02392825"},{"key":"10.1016\/S0196-6774(02)00214-6_BIB011","series-title":"Proc. ACM Symposium on Theory of Computing","first-page":"1","article-title":"Some optimal inapproximability results","author":"H\u00e5stad","year":"1997"},{"key":"10.1016\/S0196-6774(02)00214-6_BIB012","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","article-title":"The NP-completeness of edge colouring","volume":"10","author":"Holyer","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0196-6774(02)00214-6_BIB013","author":"Khanna"},{"key":"10.1016\/S0196-6774(02)00214-6_BIB014","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0020-0190(98)00034-9","article-title":"On the minimum label spanning tree problem","volume":"66","author":"Krumke","year":"1998","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0196-6774(02)00214-6_BIB015","doi-asserted-by":"crossref","first-page":"1218","DOI":"10.1109\/50.511623","article-title":"A wavelength rerouting algorithm in wide-area all-optical networks","volume":"14","author":"Lee","year":"1996","journal-title":"IEEE\/OSA J. Lightwave Technol."},{"key":"10.1016\/S0196-6774(02)00214-6_BIB016","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1016\/S0140-3664(98)00239-4","article-title":"Efficient algorithms for wavelength rerouting in WDM multi-fiber unidirectional ring networks","volume":"22","author":"Mohan","year":"1999","journal-title":"Comput. Commun."},{"key":"10.1016\/S0196-6774(02)00214-6_BIB017","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1109\/50.749380","article-title":"A time optimal wavelength rerouting for dynamic traffic in WDM networks","volume":"17","author":"Mohan","year":"1999","journal-title":"IEEE\/OSA J. Lightwave Technol."},{"key":"10.1016\/S0196-6774(02)00214-6_BIB018","series-title":"Randomized Algorithms","author":"Motwani","year":"1995"},{"key":"10.1016\/S0196-6774(02)00214-6_BIB019","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou, M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. System Sci. 43 (3) 425\u2013440","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"10.1016\/S0196-6774(02)00214-6_BIB020","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/1008293.1008294","article-title":"Planar 3-colorability is NP-complete","volume":"5","author":"Stockmeyer","year":"1973","journal-title":"SIGACT News"}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677402002146?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677402002146?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T21:25:06Z","timestamp":1554758706000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0196677402002146"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,11]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2002,11]]}},"alternative-id":["S0196677402002146"],"URL":"https:\/\/doi.org\/10.1016\/s0196-6774(02)00214-6","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[2002,11]]}}}