{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:25Z","timestamp":1759638745725},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2013,6]]},"abstract":"<jats:p>The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem \u03a0, an optimal solution OPT in I and an instance I' resulting from a local perturbation of I that consists of insertions or removals of a small number of data, we wish to use OPT to solve \u03a0 in I', either optimally or by guaranteeing an approximation ratio better than that guaranteed by an ex nihilo computation and with running time better than that needed for such a computation. We use this setting to study weighted versions of MAX P<jats:sub>k<\/jats:sub>-FREE SUBGRAPH and MAX PLANAR SUBGRAPH, which are representatives of a broad class of problems known in the literature as maximum induced hereditary subgraph problems. We also show that the techniques presented allow us to handle BIN PACKING.<\/jats:p>","DOI":"10.1142\/s1793830913600045","type":"journal-article","created":{"date-parts":[[2013,6,25]],"date-time":"2013-06-25T02:37:08Z","timestamp":1372127828000},"page":"1360004","source":"Crossref","is-referenced-by-count":2,"title":["REOPTIMIZATION UNDER VERTEX INSERTION: MAX P<sub>k<\/sub>-FREE SUBGRAPH AND MAX PLANAR SUBGRAPH"],"prefix":"10.1142","volume":"05","author":[{"given":"NICOLAS","family":"BORIA","sequence":"first","affiliation":[{"name":"PSL Research University, Universit\u00e9 Paris-Dauphine, LAMSADE, CNRS UMR 7243, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00c9R\u00d4ME","family":"MONNOT","sequence":"additional","affiliation":[{"name":"PSL Research University, Universit\u00e9 Paris-Dauphine, LAMSADE, CNRS UMR 7243, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"VANGELIS TH.","family":"PASCHOS","sequence":"additional","affiliation":[{"name":"PSL Research University, Universit\u00e9 Paris-Dauphine, LAMSADE, CNRS UMR 7243, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2013,6,24]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1002\/net.10091"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.08.003"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9419-8"},{"key":"rf9","first-page":"83","volume":"2","author":"B\u00f6ckenhauer H.-J.","year":"2007","journal-title":"Algorithmic Operations Research"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.039"},{"key":"rf14","doi-asserted-by":"crossref","first-page":"59","DOI":"10.3233\/FI-2011-528","volume":"110","author":"B\u00f6ckenhauer H.-J.","year":"2011","journal-title":"Fundamenta Informaticae"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.04.001"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.07.002"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00091"},{"key":"rf20","first-page":"86","volume":"4","author":"Escoffier B.","year":"2009","journal-title":"Algorithmic Operations Research"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1090\/S1079-6762-96-00003-0"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00042-X"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01109922"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2011.05.066"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830913600045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,29]],"date-time":"2020-07-29T01:56:54Z","timestamp":1595987814000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830913600045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":15,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2013,6,24]]},"published-print":{"date-parts":[[2013,6]]}},"alternative-id":["10.1142\/S1793830913600045"],"URL":"https:\/\/doi.org\/10.1142\/s1793830913600045","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6]]}}}