{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T17:01:48Z","timestamp":1764349308654},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,11,24]],"date-time":"2023-11-24T00:00:00Z","timestamp":1700784000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,11,24]],"date-time":"2023-11-24T00:00:00Z","timestamp":1700784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Rice University\u2019s Building Research on Inequality and Diversity to Grow Equity"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2024,3]]},"DOI":"10.1007\/s11590-023-02076-8","type":"journal-article","created":{"date-parts":[[2023,11,24]],"date-time":"2023-11-24T15:02:10Z","timestamp":1700838130000},"page":"651-661","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A polytime preprocess algorithm for the maximum independent set problem"],"prefix":"10.1007","volume":"18","author":[{"given":"Samuel","family":"Kroger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hamidreza","family":"Validi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Illya V.","family":"Hicks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,24]]},"reference":[{"key":"2076_CR1","doi-asserted-by":"crossref","unstructured":"Bondy, J., Murty, U.: Graph theory (2008)","DOI":"10.1007\/978-1-84628-970-5"},{"key":"2076_CR2","doi-asserted-by":"publisher","first-page":"1611","DOI":"10.1007\/s11590-013-0698-2","volume":"8","author":"A Buchanan","year":"2014","unstructured":"Buchanan, A., Walteros, J.L., Butenko, S., Pardalos, P.M.: Solving maximum clique in sparse graphs: an $${O} (nm+ n 2^{d\/4})$$ algorithm for $$d$$-degenerate graphs. Optim. Lett. 8, 1611\u20131617 (2014)","journal-title":"Optim. Lett."},{"issue":"3","key":"2076_CR3","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"JF Buss","year":"1993","unstructured":"Buss, J.F., Goldsmith, J.: Nondeterminism within $${P}^{*}$$. SIAM J. Comput. 22(3), 560\u2013572 (1993)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2076_CR4","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1016\/j.orl.2006.07.004","volume":"35","author":"S Butenko","year":"2007","unstructured":"Butenko, S., Trukhanov, S.: Using critical sets to solve the maximum independent set problem. Oper. Res. Lett. 35(4), 519\u2013524 (2007)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"2076_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629600","volume":"61","author":"Y Faenza","year":"2014","unstructured":"Faenza, Y., Oriolo, G., Stauffer, G.: Solving the weighted stable set problem in claw-free graphs via decomposition. J. ACM 61(4), 1\u201341 (2014)","journal-title":"J. ACM"},{"key":"2076_CR6","unstructured":"Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs (1976)"},{"key":"2076_CR7","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"key":"2076_CR8","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: 9.4 coloring perfect graphs. Geometric Algorithms and Combinatorial Optimization pp. 296\u2013298 (1988)","DOI":"10.1007\/978-3-642-97881-4"},{"issue":"4","key":"2076_CR9","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1137\/0603052","volume":"3","author":"PL Hammer","year":"1982","unstructured":"Hammer, P.L., Hansen, P., Simeone, B.: Vertices belonging to all or to no maximum stable sets of a graph. SIAM J. Algebraic Discrete Methods 3(4), 511\u2013522 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"2076_CR10","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tcs.2018.05.004","volume":"739","author":"W Li","year":"2018","unstructured":"Li, W., Zhu, B.: A $$2k$$-kernelization algorithm for vertex cover based on crown decomposition. Theoret. Comput. Sci. 739, 80\u201385 (2018)","journal-title":"Theoret. Comput. Sci."},{"key":"2076_CR11","doi-asserted-by":"crossref","unstructured":"Lokshantov, D., Vatshelle, M., Villanger, Y.: Independent set in p 5-free graphs in polynomial time. In: Proceedings of The Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 570\u2013581. SIAM (2014)","DOI":"10.1137\/1.9781611973402.43"},{"issue":"1","key":"2076_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.orl.2006.01.009","volume":"35","author":"C Mannino","year":"2007","unstructured":"Mannino, C., Oriolo, G., Ricci, F., Chandran, S.: The stable set problem and the thinness of a graph. Oper. Res. Lett. 35(1), 1\u20139 (2007)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"2076_CR13","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28(3), 284\u2013304 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"2076_CR14","first-page":"194","volume":"44","author":"D Nakamura","year":"2001","unstructured":"Nakamura, D., Tamura, A.: A revision of Minty\u2019s algorithm for finding a maximum weight stable set of a claw-free graph. J. Oper. Res. Soc. Jpn. 44(2), 194\u2013204 (2001)","journal-title":"J. Oper. Res. Soc. Jpn."},{"issue":"1","key":"2076_CR15","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., Jr.: Vertex packings: structural properties and algorithms. Math. Program. 8(1), 232\u2013248 (1975)","journal-title":"Math. Program."},{"key":"2076_CR16","doi-asserted-by":"crossref","unstructured":"Nobili, P., Sassano, A.: An $${O}(n^2 \\log n)$$ algorithm for the weighted stable set problem in claw-free graphs. arXiv preprint arXiv:1501.05775 (2015)","DOI":"10.1016\/j.dam.2013.10.015"},{"key":"2076_CR17","unstructured":"Robson, J.M.: Finding a maximum independent set in time $${O} (2^{n\/4})$$. Tech. rep., Technical Report 1251-01, LaBRI, Universit\u00e9 Bordeaux I (2001)"},{"issue":"3","key":"2076_CR18","doi-asserted-by":"publisher","first-page":"1309","DOI":"10.1287\/ijoc.2021.1136","volume":"34","author":"H Salemi","year":"2022","unstructured":"Salemi, H., Buchanan, A.: Solving the distance-based critical node problem. INFORMS J. Comput. 34(3), 1309\u20131326 (2022)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"2076_CR19","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N Sbihi","year":"1980","unstructured":"Sbihi, N.: Algorithme de recherche d\u2019un stable de cardinalit\u00e9 maximum dans un graphe sans \u00e9toile. Discret. Math. 29(1), 53\u201376 (1980)","journal-title":"Discret. Math."},{"issue":"6","key":"2076_CR20","doi-asserted-by":"publisher","first-page":"1866","DOI":"10.1287\/opre.2019.1970","volume":"68","author":"JL Walteros","year":"2020","unstructured":"Walteros, J.L., Buchanan, A.: Why is maximum clique often easy in practice? Oper. Res. 68(6), 1866\u20131895 (2020)","journal-title":"Oper. Res."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-02076-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-023-02076-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-02076-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,27]],"date-time":"2024-02-27T19:27:39Z","timestamp":1709062059000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-023-02076-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,24]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["2076"],"URL":"https:\/\/doi.org\/10.1007\/s11590-023-02076-8","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,24]]},"assertion":[{"value":"24 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}