{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:10Z","timestamp":1740109330861,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T00:00:00Z","timestamp":1726099200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T00:00:00Z","timestamp":1726099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["772346"],"award-info":[{"award-number":["772346"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"IDEAS NCBR"},{"name":"Network Sciences and Technologies"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,11]]},"DOI":"10.1007\/s00453-024-01268-7","type":"journal-article","created":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T14:04:51Z","timestamp":1726149891000},"page":"3518-3578","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Ultimate Greedy Approximation of Independent Sets in Subcubic Graphs"],"prefix":"10.1007","volume":"86","author":[{"given":"Piotr","family":"Krysta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8074-0241","authenticated-orcid":false,"given":"Mathieu","family":"Mari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nan","family":"Zhi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,12]]},"reference":[{"key":"1268_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237, 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"1268_CR2","doi-asserted-by":"publisher","first-page":"27","DOI":"10.4086\/toc.2011.v007a003","volume":"7","author":"P Austrin","year":"2011","unstructured":"Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. Theory Comput. 7, 27\u201343 (2011)","journal-title":"Theory Comput."},{"key":"1268_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Gupta, A., Guruganesh, G.: On the Lov\u00e1sz theta function for independent sets in sparse graphs. In: Proceedings of the forty-seventh annual ACM symposium on theory of computing, STOC \u201915, pp. 193\u2013200. ACM, New York, NY, USA (2015)","DOI":"10.1145\/2746539.2746607"},{"key":"1268_CR4","volume-title":"Graphs and hypergraphs","author":"C Berge","year":"1973","unstructured":"Berge, C.: Graphs and hypergraphs. North-Holland, Ansterdam (1973)"},{"key":"1268_CR5","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s002240000113","volume":"32","author":"P Berman","year":"1999","unstructured":"Berman, P., Fujito, T.: On approximation properties of the independent set problem for low degree graphs. Theory Comput. Syst. 32, 115\u2013132 (1999)","journal-title":"Theory Comput. Syst."},{"key":"1268_CR6","unstructured":"Berman, P., F\u00fcrer, M.: Approximating maximum independent set in bounded degree graphs. In: Proceedings of the fifth annual ACM-SIAM symposium on discrete algorithms, SODA \u201994, pp. 365\u2013371. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1994)pp. 365\u2013371"},{"key":"1268_CR7","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0020-0190(96)00208-6","volume":"61","author":"HL Bodlaender","year":"1997","unstructured":"Bodlaender, H.L., Thilikos, D.M., Yamazaki, K.: It is hard to know when greedy is good for finding independent sets. Inf. Process. Lett. 61, 101\u2013106 (1997)","journal-title":"Inf. Process. Lett."},{"key":"1268_CR8","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R Boppana","year":"1992","unstructured":"Boppana, R., Halld\u00f3rsson, M.M.: Approximating maximum independent sets by excluding subgraphs. BIT Numer. Math. 32, 180\u2013196 (1992)","journal-title":"BIT Numer. Math."},{"key":"1268_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2811255","volume":"63","author":"SO Chan","year":"2016","unstructured":"Chan, S.O.: Approximation resistance from pairwise-independent subgroups. J. ACM 63, 1\u201332 (2016)","journal-title":"J. ACM"},{"key":"1268_CR10","doi-asserted-by":"crossref","unstructured":"Chlebik, M., Chlebikova, J.: Inapproximability results for bounded variants of optimization problems. In: Electronic colloquium on computational complexity (ECCC), report, vol. 26, pp. 27\u201338 (2003)","DOI":"10.1007\/978-3-540-45077-1_4"},{"key":"1268_CR11","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-540-27796-5_5","volume-title":"Structural information and communication complexity","author":"M Chleb\u00edk","year":"2004","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: On approximability of the independent set problem for low degree graphs. In: Kr\u00e1lovic, R., S\u00fdkora, O. (eds.) Structural information and communication complexity, pp. 47\u201356. Springer, Berlin, Heidelberg (2004)"},{"key":"1268_CR12","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1142\/S0129054118500168","volume":"29","author":"A Darmann","year":"2018","unstructured":"Darmann, A., D\u00f6cker, J., Dorn, B.: The monotone satisfiability problem with bounded variable appearances. Int. J. Found. Comput. Sci. 29, 979\u2013993 (2018)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1268_CR13","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0893-9659(97)00044-X","volume":"10","author":"M Demange","year":"1997","unstructured":"Demange, M., Paschos, V.: Improved approximations for maximum independent set via approximation chains. Appl. Math. Lett. 10, 105\u2013110 (1997)","journal-title":"Appl. Math. Lett."},{"key":"1268_CR14","first-page":"249","volume":"21","author":"P Erd\u0151s","year":"1970","unstructured":"Erd\u0151s, P.: On the graph theorem of Tur\u00e1n. Mat. Lapok 21, 249\u2013251 (1970)","journal-title":"Mat. Lapok"},{"key":"1268_CR15","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1137\/S089548010240415X","volume":"18","author":"U Feige","year":"2004","unstructured":"Feige, U.: Approximating maximum clique by removing subgraphs. SIAM J. Discrete Math. 18, 219\u2013225 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"1268_CR16","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1002\/rsa.3240050504","volume":"5","author":"AM Frieze","year":"1994","unstructured":"Frieze, A.M., Suen, S.: On the independence number of random cubic graphs. Random Struct. Algorithms 5, 649\u2013664 (1994)","journal-title":"Random Struct. Algorithms"},{"key":"1268_CR17","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1, 237\u2013267 (1976)","journal-title":"Theoret. Comput. Sci."},{"key":"1268_CR18","unstructured":"Hajnal, A., Szemer\u00e9di, E.: Proof of a conjecture of P. Erd\u0151s. In: Erd\u0151s, P., R\u00e9nyi, A., S\u00f3s, V. (eds.) Combinatorial Theory and its Applications, pp. 601\u2013623. North-Holland, Amsterdam (1970)"},{"key":"1268_CR19","unstructured":"Halld\u00f3rsson, M.M.: Private communication. Erratum. https:\/\/www.ru.is\/kennarar\/mmh\/papers\/hy95-errata.html, (2019)"},{"key":"1268_CR20","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. In: Proceedings of the twenty-sixth annual ACM symposium on theory of computing, STOC 1994, Montr\u00e9al, Qu\u00e9bec, Canada, 23-25 May 1994, pp. 439\u2013448 (1994)","DOI":"10.1145\/195058.195221"},{"key":"1268_CR21","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Radhakrishnan, J.: Improved approximations of independent sets in bounded-degree graphs. In: Algorithm Theory\u2014SWAT \u201994, 4th Scandinavian workshop on algorithm theory, Aarhus, Denmark, July 6-8, 1994, Proceedings, pp. 195\u2013206 (1994)","DOI":"10.1007\/3-540-58218-5_18"},{"key":"1268_CR22","first-page":"475","volume":"1","author":"MM Halld\u00f3rsson","year":"1994","unstructured":"Halld\u00f3rsson, M.M., Radhakrishnan, J.: Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Nord. J. Comput. 1, 475\u2013492 (1994)","journal-title":"Nord. J. Comput."},{"key":"1268_CR23","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02523693","volume":"18","author":"MM Halld\u00f3rsson","year":"1997","unstructured":"Halld\u00f3rsson, M.M., Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18, 145\u2013163 (1997)","journal-title":"Algorithmica"},{"key":"1268_CR24","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/BFb0015418","volume-title":"Algorithms and computations\u2013ISAAC \u201995, in LNCS","author":"MM Halld\u00f3rsson","year":"1995","unstructured":"Halld\u00f3rsson, M.M., Yoshihara, K.: Greedy approximations of independent sets in low degree graphs. In: Staples, J., Eades, P., Katoh, N., Moffat, A. (eds.) Algorithms and computations\u2013ISAAC \u201995, in LNCS, vol. 1004, pp. 152\u2013161. Springer, Berlin, Heidelberg (1995)"},{"key":"1268_CR25","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E Halperin","year":"2002","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31, 1608\u20131623 (2002)","journal-title":"SIAM J. Comput."},{"key":"1268_CR26","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"DS Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discret. Appl. Math. 6, 243\u2013254 (1983)","journal-title":"Discret. Appl. Math."},{"key":"1268_CR27","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within$$n^{1 -\\epsilon }$$, Acta Math., 182, pp. 105\u2013142 (1999)","DOI":"10.1007\/BF02392825"},{"key":"1268_CR28","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-sat. J. Comput. Syst. Sci. 62, 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"1268_CR29","unstructured":"Johnson, D.S.: Worst case behavior of graph coloring algorithms. In: Proceedings of the 5th southeastern conference on combinatorics, graph theory and computing, Congressus Numerantium X, pp. 513\u2014527 (1974)"},{"key":"1268_CR30","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a symposium on the complexity of computer computations, held March 20-22, 1972, at the IBM Thomas J, pp. 85\u2013103. Watson Research Center, Yorktown Heights, New York, (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1268_CR31","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1137\/S0097539795286612","volume":"28","author":"S Khanna","year":"1998","unstructured":"Khanna, S., Motwani, R., Sudan, M., Vazirani, U.: On syntactic versus computational views of approximability. SIAM J. Comput. 28, 164\u2013191 (1998)","journal-title":"SIAM J. Comput."},{"key":"1268_CR32","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0095-8956(75)90089-1","volume":"19","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: Three short proofs in graph theory. J. Comb. Theory Ser. B 19, 269\u2013271 (1975)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1268_CR33","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF01874388","volume":"1","author":"C McDiarmid","year":"1984","unstructured":"McDiarmid, C.: Colouring random graphs. Ann. Oper. Res. 1, 183\u2013200 (1984)","journal-title":"Ann. Oper. Res."},{"key":"1268_CR34","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packings: structural properties and algorithms. Math. Program. 8, 232\u2013248 (1975)","journal-title":"Math. Program."},{"key":"1268_CR35","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0012-365X(83)90273-X","volume":"46","author":"JB Shearer","year":"1983","unstructured":"Shearer, J.B.: A note on the independence number of triangle-free graphs. Discret. Math. 46, 83\u201387 (1983)","journal-title":"Discret. Math."},{"key":"1268_CR36","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1137\/0403025","volume":"3","author":"HU Simon","year":"1990","unstructured":"Simon, H.U.: On approximate solutions for combinatorial optimization problems. SIAM J. Discrete Math. 3, 294\u2013310 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"1268_CR37","first-page":"436","volume":"48","author":"P Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n, P.: An extremal problem in graph theory. Mat. Fiz. Lapok 48, 436\u2013452 (1941)","journal-title":"Mat. Fiz. Lapok"},{"key":"1268_CR38","volume-title":"A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum, 81\u201311217-9","author":"V Wei","year":"1981","unstructured":"Wei, V.: A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum, 81\u201311217-9. Murray Hill, NJ (1981)"},{"key":"1268_CR39","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the thirty-eighth annual ACM symposium on theory of computing, STOC \u201906, pp. 681\u2013690. ACM, New York, NY (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01268-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01268-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01268-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T09:01:43Z","timestamp":1728810103000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01268-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,12]]},"references-count":39,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["1268"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01268-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,9,12]]},"assertion":[{"value":"13 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}