Reoptimization of maximum weight induced hereditary subgraph problems
Boria, Nicolas; Paschos, Vangelis; Monnot, Jérôme (2013), Reoptimization of maximum weight induced hereditary subgraph problems, Theoretical Computer Science, 514, p. 61-74. http://dx.doi.org/10.1016/j.tcs.2012.10.037
TypeArticle accepté pour publication ou publié
Journal nameTheoretical Computer Science
MetadataShow full item record
Abstract (EN)The reoptimization issue studied in this paper can be described as follows: given aninstance I of some problem Π, an optimal solution O P T for Π in I and an instance I ′ resultingfrom a local perturbation of I that consists of insertions or removals of a small number ofdata, we wish to use O P T in order to solve Π in I ′, either optimally or by guaranteeingan approximation ratio better than that guaranteed by an ex nihilo computation and withrunning time better that that needed for such a computation. We use this setting in order tostudy weighted versions of several representatives of a broad class of problems known in theliterature as maximum induced hereditary subgraph problems. The main problems studiedare max independent set, max k -colorable subgraph, max Pk-free subgraph, maxsplit subgraph and max planar subgraph. We also show, how the techniques presentedallow us to handle also bin packing.
Subjects / Keywordsreoptimization
Showing items related by title and author.