{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:40:28Z","timestamp":1772372428386,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1999,7,1]],"date-time":"1999-07-01T00:00:00Z","timestamp":930787200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1999,7,1]],"date-time":"1999-07-01T00:00:00Z","timestamp":930787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Optimization and Applications"],"published-print":{"date-parts":[[1999,7]]},"DOI":"10.1023\/a:1008765214400","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T11:37:32Z","timestamp":1040557052000},"page":"157-169","source":"Crossref","is-referenced-by-count":8,"title":["A Note on the Approximation of a Minimum-Weight Maximal Independent Set"],"prefix":"10.1007","volume":"14","author":[{"given":"Marc","family":"Demange","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"203792_CR1","doi-asserted-by":"crossref","unstructured":"M. Bellare, O. Goldreich, and M. Sudan, Free bits, PCPs and non-approximability: towards tight results, in Proc. of 36th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, pp. 422\u2013431, 1995.","DOI":"10.1109\/SFCS.1995.492573"},{"key":"203792_CR2","volume-title":"Graphs and Hypergraphs","author":"C. Berge","year":"1973","unstructured":"C. Berge, Graphs and Hypergraphs, North Holland: Amsterdam, 1973."},{"key":"203792_CR3","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"V. Chv\u00e1tal, A Greedy Heuristic for the Set Covering Problem, Mathematics of Operations Research, vol. 4, pp. 233\u2013235, 1979.","journal-title":"Mathematics of Operations Research"},{"key":"203792_CR4","doi-asserted-by":"crossref","unstructured":"P. Crescenzi and V. Kann, A Compendium of NP Optimization Problems, available in electronic form at http:\/\/www.nada.kth.se\/~viggo\/problemlist\/compendium.html, 1996.","DOI":"10.1007\/3-540-63248-4_10"},{"key":"203792_CR5","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0893-9659(97)00044-X","volume":"10","author":"M. Demange","year":"1997","unstructured":"M. Demange and V.T. Paschos, Improved Approximations for Maximum Independent Set via Approximation Chain, Appl. Math. Lett., vol. 10, pp. 105\u2013110, 1997.","journal-title":"Appl. Math. Lett."},{"key":"203792_CR6","doi-asserted-by":"crossref","unstructured":"U. Feige and J. Kilian, Zero Knowledge and the Chromatic Number, in Proc. 11th Annual IEEE Conf. Comp. Complexity, pp. 278\u2013287, 1996.","DOI":"10.1109\/CCC.1996.507690"},{"key":"203792_CR7","volume-title":"Computers and Intractability: a Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, Freeman: San Francisco, 1979."},{"key":"203792_CR8","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"M.M. Halld\u00f3rsson, A Still Better Performance Guarantee for Approximate Graph Coloring, Information Processing Letters, vol. 45, pp. 19\u201323, 1993.","journal-title":"Information Processing Letters"},{"key":"203792_CR9","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"M.M. Halld\u00f3rsson, Approximating the Minimum Maximal Independence Number, Information Processing Letters, vol. 46, pp. 169\u2013172, 1993.","journal-title":"Information Processing Letters"},{"key":"203792_CR10","series-title":"Technical Report","volume-title":"Approximation via Partitioning","author":"M.M. Halld\u00f3rsson","year":"1995","unstructured":"M.M. Halld\u00f3rsson, Approximation via Partitioning, Technical Report IS-RR-95\u20130003F, School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku, 1995."},{"key":"203792_CR11","doi-asserted-by":"crossref","unstructured":"M.M. Halld\u00f3rsson and J. Radhakrishnan, Greed is Good: Approximation Independent Set in Sparse and Bounded Degree Graphs, in Proc. 26th Ann. ACM Symp. on Theory of Computing, pp. 439\u2013448, 1994.","DOI":"10.1145\/195058.195221"},{"key":"203792_CR12","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Clique is Hard to Approximate within n\n1\u2212\u03b5\n, in Proc. 37th Annual IEEE Symp. Found. Comput. Sci., pp. 627\u2013636, 1996.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"203792_CR13","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0020-0190(91)90188-N","volume":"37","author":"R.W. Irving","year":"1991","unstructured":"R.W. Irving, On Approximating the Minimum Independent Dominating Set, Information Processing Letters, vol. 37, pp. 197\u2013200, 1991.","journal-title":"Information Processing Letters"},{"key":"203792_CR14","first-page":"513","volume-title":"Proc. 5th Sountheastern Conf. on Combinatorics, Graph Theory and Computing","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson, Worst-case Behaviour of Graph Coloring Algorithms, in Proc. 5th Sountheastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica Publ.: Winnipeg, Ont., pp. 513\u2013527, 1974."},{"key":"203792_CR15","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis, On the Hardness of Approximating Minimization Problems, Proc. STOC'93, pp. 286\u2013293, 1993.","DOI":"10.1145\/167088.167172"},{"key":"203792_CR16","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0403025","volume":"3","author":"H.U. Simon","year":"1990","unstructured":"H.U. Simon, On Approximate Solutions for Combinatorial Optimization Problems, SIAM J. Disc. Math., vol. 3, pp. 294\u2013310, 1990.","journal-title":"SIAM J. Disc. Math."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1008765214400.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1008765214400\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1008765214400.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,13]],"date-time":"2025-07-13T03:37:11Z","timestamp":1752377831000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1008765214400"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,7]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1999,7]]}},"alternative-id":["203792"],"URL":"https:\/\/doi.org\/10.1023\/a:1008765214400","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,7]]}}}