{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T17:07:29Z","timestamp":1725815249186},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662460771"},{"type":"electronic","value":"9783662460788"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46078-8_2","type":"book-chapter","created":{"date-parts":[[2015,1,14]],"date-time":"2015-01-14T14:54:29Z","timestamp":1421247269000},"page":"14-23","source":"Crossref","is-referenced-by-count":0,"title":["Progress (and Lack Thereof) for Graph Coloring Approximation Problems"],"prefix":"10.1007","author":[{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.jda.2012.07.001","volume":"16","author":"J. Araujo","year":"2012","unstructured":"Araujo, J., Bermond, J.-C., Giroire, F., Havet, F., Mazauric, D., Modrzejewski, R.: Weighted improper colouring. Journal of Discrete Algorithms\u00a016, 53\u201366 (2012)","journal-title":"Journal of Discrete Algorithms"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems. In: FOCS, pp. 14\u201323 (1992)","DOI":"10.1109\/SFCS.1992.267823"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Halld\u00f3rsson, M.M.: A note on vertex coloring edge-weighted digraphs. Preprints on graph, hypergraphs and computing, Institute Mittag-Leffler (2014)","DOI":"10.1016\/j.ipl.2015.05.007"},{"issue":"4","key":"2_CR4","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/BF01840398","volume":"5","author":"B. Berger","year":"1990","unstructured":"Berger, B., Rompel, J.: A better performance guarantee for approximate graph coloring. Algorithmica\u00a05(4), 459\u2013466 (1990)","journal-title":"Algorithmica"},{"issue":"1","key":"2_CR5","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0020-0190(96)00190-1","volume":"61","author":"A. Blum","year":"1997","unstructured":"Blum, A., Karger, D.: An $\\tilde O(n^{3\/14})$ -coloring algorithm for 3-colorable graphs. Information Processing Letters\u00a061(1), 49\u201353 (1997)","journal-title":"Information Processing Letters"},{"key":"2_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-52846-6_74","volume-title":"SWAT \u201990","author":"R.B. Boppana","year":"1990","unstructured":"Boppana, R.B., Halld\u00f3rsson, M.M.: Approximating maximum independent sets by excluding subgraphs. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol.\u00a0447, pp. 13\u201325. Springer, Heidelberg (1990)"},{"key":"2_CR7","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. J.\u00a0Comput. Syst. Sci.\u00a057, 187\u2013199 (1998)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"2_CR8","unstructured":"Halld\u00f3rsson, M.M.: A still better performance guarantee for approximate graph coloring. Technical Report 90\u201344, DIMACS (1990)"},{"key":"2_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. Inform. Process. Lett.\u00a045, 19\u201323 (1993)","journal-title":"Inform. Process. Lett."},{"key":"2_CR10","unstructured":"Halld\u00f3rsson, M.M.: Approximation via partitioning. Research Report IS-RR-95-0003F, JAIST (1995)"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Holzer, S., Mitra, P., Wattenhofer, R.: The power of non-uniform wireless power. In: SODA (2013)","DOI":"10.1137\/1.9781611973105.114"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Mitra, P.: Wireless Capacity with Oblivious Power in General Metrics. In: SODA (2011)","DOI":"10.1137\/1.9781611973082.119"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2013.09.035","volume":"553","author":"M.M. Halld\u00f3rsson","year":"2014","unstructured":"Halld\u00f3rsson, M.M., Mitra, P.: Wireless capacity with arbitrary gain matrix. Theor. Comput. Sci.\u00a0553, 57\u201363 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/978-3-642-02927-1_44","volume-title":"Automata, Languages and Programming","author":"M.M. Halld\u00f3rsson","year":"2009","unstructured":"Halld\u00f3rsson, M.M., Wattenhofer, R.: Wireless Communication Is in APX. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 525\u2013536. Springer, Heidelberg (2009)"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Hoefer, M., Kesselheim, T., V\u00f6cking, B.: Approximation algorithms for secondary spectrum auctions. In: SPAA, pp. 177\u2013186 (2011)","DOI":"10.1145\/1989493.1989520"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Hua, Q.-S., Lau, F.: Exact and approximate link scheduling algorithms under the physical interference model. In: FOMC, pp. 45\u201354. ACM (2008)","DOI":"10.1145\/1400863.1400874"},{"key":"2_CR17","unstructured":"Johnson, D.S.: Worst case behavior of graph coloring algorithms. In: Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing. Congressus Numerantium X, pp. 513\u2013527 (1974)"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Kesselheim, T.: A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model. In: SODA (2011)","DOI":"10.1137\/1.9781611973082.120"},{"key":"2_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-642-15763-9_16","volume-title":"Distributed Computing","author":"T. Kesselheim","year":"2010","unstructured":"Kesselheim, T., V\u00f6cking, B.: Distributed contention resolution in wireless networks. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol.\u00a06343, pp. 163\u2013178. Springer, Heidelberg (2010)"},{"key":"2_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/11786986_21","volume-title":"Automata, Languages and Programming","author":"S. Khot","year":"2006","unstructured":"Khot, S., Ponnuswami, A.K.: Better inapproximability results for maxClique, chromatic number and min-3Lin-deletion. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 226\u2013237. Springer, Heidelberg (2006)"},{"issue":"1","key":"2_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"IT-25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory\u00a0IT-25(1), 1\u20137 (1979)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"4","key":"2_CR22","first-page":"729","volume":"30","author":"A. Wigderson","year":"1983","unstructured":"Wigderson, A.: Improving the performance guarantee for approximate graph coloring. J.\u00a0ACM\u00a030(4), 729\u2013735 (1983)","journal-title":"J.\u00a0ACM"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2015: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46078-8_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,26]],"date-time":"2022-04-26T20:48:24Z","timestamp":1651006104000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46078-8_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662460771","9783662460788"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46078-8_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}