{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:39:29Z","timestamp":1787510369967,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540662518","type":"print"},{"value":"9783540484813","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48481-7_35","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T19:49:40Z","timestamp":1193514580000},"page":"402-413","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Approximation Algorithms for the Achromatic Number"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Krysta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Krzysztof","family":"Lory\u015b","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2003,1,14]]},"reference":[{"key":"35_CR1","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0020-0190(89)90221-4","volume":"31","author":"H. L. Bodlaender","year":"1989","unstructured":"H. L. Bodlaender, Achromatic Number is NP-complete for Cographs and Interval Graphs, Information Processing Letters, 31: 135\u2013138, 1989.","journal-title":"Information Processing Letters"},{"key":"35_CR2","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"B. Bollob\u00e1s, Extremal Graph Theory, Academic Press, London, 1978."},{"key":"35_CR3","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1002\/(SICI)1097-0118(199711)26:3<129::AID-JGT3>3.0.CO;2-T","volume":"26","author":"N. Cairnie","year":"1997","unstructured":"N. Cairnie and K. J. Edwards, Some Results on the Achromatic Number, Journal of Graph Theory, 26: 129\u2013136, 1997.","journal-title":"Journal of Graph Theory"},{"key":"35_CR4","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S0012-365X(97)00278-1","volume":"188","author":"N. Cairnie","year":"1998","unstructured":"N. Cairnie and K. J. Edwards, The Achromatic Number of Bounded Degree Trees, Discrete Mathematics, 188: 87\u201397, 1998.","journal-title":"Discrete Mathematics"},{"key":"35_CR5","unstructured":"A. Chaudhary and S. Vishwanathan, Approximation Algorithms for the Achromatic Number, Proc. 8th ACM-SIAM Symposium on Discrete Algorithms, 558\u2013563, 1997."},{"key":"35_CR6","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990."},{"key":"35_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0095-8956(86)90062-6","volume":"40","author":"M. Farber","year":"1986","unstructured":"M. Farber, G. Hahn, P. Hell and D. Miller, Concerning the Achromatic Number of Graphs, Journal of Combinatorial Theory, Series B, 40: 21\u201339, 1986.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"35_CR8","first-page":"453","volume":"26","author":"F. Harary","year":"1967","unstructured":"F. Harary, S. Hedetniemi and G. Prins, An Interpolation Theorem for Graphical Homomorphisms, Portugaliae Mathematica, 26: 453\u2013462, 1967.","journal-title":"Portugaliae Mathematica"},{"key":"35_CR9","volume-title":"Lecture Notes on Approximation Algorithms","author":"R. Motwani","year":"1992","unstructured":"R. Motwani, Lecture Notes on Approximation Algorithms, Department of Computer Science, Stanford University, Stanford, 1992."},{"key":"35_CR10","volume-title":"The Four-Color Problem: assaults and conquest","author":"T. L. Saaty","year":"1986","unstructured":"T. L. Saaty and P. C. Kainen, The Four-Color Problem: assaults and conquest, Dover Publishers, NewYork, 1986."},{"key":"35_CR11","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M. Yannakakis","year":"1980","unstructured":"M. Yannakakis and F. Gavril, Edge Dominating Sets in Graphs, SIAM Journal on Applied Mathematics, 38: 364\u2013372, 1980.","journal-title":"SIAM Journal on Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA\u2019 99"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48481-7_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T14:11:43Z","timestamp":1551017503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48481-7_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662518","9783540484813"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-48481-7_35","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1999]]}}}