{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T16:44:57Z","timestamp":1749487497004},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2001,9,1]],"date-time":"2001-09-01T00:00:00Z","timestamp":999302400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Oper Res Int J"],"published-print":{"date-parts":[[2001,9]]},"DOI":"10.1007\/bf02936352","type":"journal-article","created":{"date-parts":[[2008,8,24]],"date-time":"2008-08-24T03:53:05Z","timestamp":1219549985000},"page":"213-224","source":"Crossref","is-referenced-by-count":1,"title":["On-line independent set by coloring vertices"],"prefix":"10.1007","volume":"1","author":[{"given":"Vangelis Th.","family":"Paschos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"BF02936352_CR1","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1007\/s004530010071","volume":"29","author":"G. Ausiello","year":"2001","unstructured":"Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L. and Talamo, M. (2001).Algorithms for the on-line traveling salesman problem. Algorithmica 29(4), 560\u2013581.","journal-title":"Algorithmica"},{"key":"BF02936352_CR2","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O. and Sudan, M. (1998).Free bits and non-approximability towards tight results. SIAM J. Comput., 27, 804\u2013915.","journal-title":"SIAM J. Comput."},{"key":"BF02936352_CR3","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/BF01840398","volume":"5","author":"B. Berger","year":"1990","unstructured":"Berger, B. and Rompel J. (1990). A better performance guarantee for approximate graph coloring. Algorithmica 5, 459\u2013466.","journal-title":"Algorithmica"},{"key":"BF02936352_CR4","unstructured":"Blum, A. (1991). Algorithms for approximate graph coloring. Ph.D. thesis, MIT, Laboratory for Computer Science, Cambridge Mass., USA Technical Report MIT\/LCS\/TR-506."},{"issue":"3","key":"BF02936352_CR5","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1145\/176584.176586","volume":"41","author":"A. Blum","year":"1994","unstructured":"Blum, A. (1994). New approximation algorithms for graph coloring. J. Assoc. Comput. Mach., 41(3), 470\u2013516.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02936352_CR6","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0020-0190(96)00190-1","volume":"61","author":"A. Blum","year":"1997","unstructured":"Blum, A. and Karger, D. (1997). An \u00d5(n3\/14) coloring for 3-colorable graphs. Inform. Process. Lett. 61, 49\u201353.","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"BF02936352_CR7","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"B.B. Boppana","year":"1992","unstructured":"Boppana, B.B. and Hald\u2019 orsson, M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT, 32(2), 180\u2013196.","journal-title":"BIT"},{"key":"BF02936352_CR8","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R. L. Brooks","year":"1941","unstructured":"Brooks, R. L. (1941). On coloring the nodes of a network. Math. Proc. Cambridge Philos. Soc., 37, 194\u2013197.","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"BF02936352_CR9","doi-asserted-by":"crossref","unstructured":"Demange, M., Paradon, X. and Paschos, V.T. (2000). On-line maximum-order induced hereditary subgraph problems In V. Hlavac, K. G. Jeffery, and J. Wiedermann, (eds.) SOFSEM 2000--Theory and Practice of Informatics, volume 1963 of Lecture Notes in Computer Science, 326\u2013334. Springer-Verlag.","DOI":"10.1007\/3-540-44411-4_21"},{"key":"BF02936352_CR10","first-page":"327","volume":"92","author":"R. El-Yaniv","year":"1992","unstructured":"El-Yaniv, R., Fiat, A., Karp, R. and Turpin, G. (1992). Competitive analysis of financial games. In Proc. FOCS\u2019 92, 327\u2013333.","journal-title":"Proc. FOCS\u2019"},{"key":"BF02936352_CR11","doi-asserted-by":"crossref","unstructured":"Feige, U. and Kilian, J. (1996). Zero knowledge and the chromatic number. In Proc. Conference on Computational Complexity, 278\u2013287. Fiat, A. et al., (eds.) Online algorithms: the state of the art, volume 1442 of Lecture Notes in Computer Science. Springer-Verlag (1998).","DOI":"10.1109\/CCC.1996.507690"},{"key":"BF02936352_CR12","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1002\/jgt.3190120212","volume":"12","author":"A. Gyarfas","year":"1998","unstructured":"Gyarfas, A. and Lehel, J. (1998). Online and first-fit colorings of graphs. J. Graph Theo., 12, 217\u2013227.","journal-title":"J. Graph Theo."},{"issue":"1","key":"BF02936352_CR13","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M.M. Halldorsson","year":"1993","unstructured":"Halldorsson, M.M. (1993). A still better performance guarantee for approximate graph coloring. Inform. Process. Lett., 45(1), 19\u201323.","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"BF02936352_CR14","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0304-3975(94)90157-0","volume":"130","author":"M.M. Halldorsson","year":"1994","unstructured":"Halldorsson, M.M. and Szegedy, M. (1994). Lower bounds for on-line graph coloring. Theoret. Comput. Sci., 130(1), 163\u2013174.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02936352_CR15","unstructured":"Irani, S. and Karlin, A.R. (1997). Online computation. In D. S. Hochbaum, (ed.) Approximation algorithms for NP-hard problems, chapter 13, 521\u2013 565. PWS Publishing Company (1997)."},{"issue":"2","key":"BF02936352_CR16","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D. Karger","year":"1998","unstructured":"Karger, D., Motwani, R. and Sudan, M. (1998). Approximate graph coloring by semidefinite programming. J. Assoc. Comput. Mach., 45(2), 246\u2013265.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02936352_CR17","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M. (1972). Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher, (eds.) Complexity of computer computations, 85\u2013103. Plenum Press, New York."},{"key":"BF02936352_CR18","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0095-8956(75)90089-1","volume":"19","author":"L. Lovasz","year":"1975","unstructured":"Lovasz, L. Three short proofs in graph theory. J. Combin. Theory Ser. B, 19, 269\u2013271 (1975).","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1\u20133","key":"BF02936352_CR19","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0012-365X(89)90096-4","volume":"75","author":"L. Lovasz","year":"1989","unstructured":"Lovasz, L., Saks, M. and Trotter, W.T. (1989). An on-line graph coloring algorithm with sublinear performance ratio. Discrete Math., 75(1\u20133), 319\u2013325.","journal-title":"Discrete Math."},{"issue":"2","key":"BF02936352_CR20","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. Sleator","year":"1985","unstructured":"Sleator, D. and Tarjan, R. (1985). Amortized efficiency of list update and paging rules. Commun. ACM, 28(2), 202\u2013208.","journal-title":"Commun. ACM"},{"issue":"4","key":"BF02936352_CR21","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1145\/2157.2158","volume":"30","author":"A. Wigderson","year":"1983","unstructured":"Wigderson, A. (1983). Improving the performance guarantee for approximate graph coloring. J. Assoc. Comput. Mach., 30(4), 729\u2013735.","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Operational Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02936352.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02936352\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02936352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,7]],"date-time":"2020-05-07T22:23:09Z","timestamp":1588890189000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02936352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,9]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2001,9]]}},"alternative-id":["BF02936352"],"URL":"https:\/\/doi.org\/10.1007\/bf02936352","relation":{},"ISSN":["1109-2858","1866-1505"],"issn-type":[{"value":"1109-2858","type":"print"},{"value":"1866-1505","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,9]]}}}