{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T22:24:51Z","timestamp":1778797491512,"version":"3.51.4"},"reference-count":9,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61222201"],"award-info":[{"award-number":["61222201"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11531011"],"award-info":[{"award-number":["11531011"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013286","name":"SRFDP","doi-asserted-by":"crossref","award":["20126501110001"],"award-info":[{"award-number":["20126501110001"]}],"id":[{"id":"10.13039\/501100013286","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Xingjiang Talent Youth Project","award":["2013711011"],"award-info":[{"award-number":["2013711011"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2016,6]]},"abstract":"<jats:p> Given a graph [Formula: see text] and an independent set [Formula: see text] of [Formula: see text], the 0\u20131 inverse maximum independent set problem (IMIS[Formula: see text]) is to delete as few vertices as possible such that [Formula: see text] becomes a maximum independent set of [Formula: see text]. It is known that IMIS[Formula: see text] is NP-hard even when the given independent set has a bounded size. In this paper, we present linear-time algorithms for IMIS[Formula: see text] on forests and unicyclic graphs. <\/jats:p>","DOI":"10.1142\/s1793830916500191","type":"journal-article","created":{"date-parts":[[2016,1,14]],"date-time":"2016-01-14T11:25:10Z","timestamp":1452770710000},"page":"1650019","source":"Crossref","is-referenced-by-count":1,"title":["The 0\u20131 inverse maximum independent set problem on forests and unicyclic graphs"],"prefix":"10.1142","volume":"08","author":[{"given":"Shuaifu","family":"Liu","sequence":"first","affiliation":[{"name":"College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang 830046, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4191-7598","authenticated-orcid":false,"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Mathematics Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang 321004, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2016,5,26]]},"reference":[{"key":"S1793830916500191BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585693"},{"key":"S1793830916500191BIB002","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008360312607"},{"key":"S1793830916500191BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.03.015"},{"key":"S1793830916500191BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2008.01.003"},{"key":"S1793830916500191BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/s10288-011-0194-4"},{"key":"S1793830916500191BIB006","volume-title":"Vangelis Th. Paschos, Paradigms of Combinatorial Optimization (Problems and New Approaches)","author":"Demange M.","year":"2010"},{"key":"S1793830916500191BIB007","volume-title":"Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"S1793830916500191BIB008","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038914.26975.9b"},{"key":"S1793830916500191BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2013.03.001"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830916500191","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,22]],"date-time":"2019-09-22T05:41:41Z","timestamp":1569130901000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830916500191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,26]]},"references-count":9,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2016,5,26]]},"published-print":{"date-parts":[[2016,6]]}},"alternative-id":["10.1142\/S1793830916500191"],"URL":"https:\/\/doi.org\/10.1142\/s1793830916500191","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,26]]}}}