Reoptimization under Vertex Insertion: Max Pk-Free Subgraph and Max Planar Subgraph
Boria, Nicolas; Monnot, Jérôme; Paschos, Vangelis (2013), Reoptimization under Vertex Insertion: Max Pk-Free Subgraph and Max Planar Subgraph, Discrete Mathematics, Algorithms and Applications, 05, 02, p. n°1360004. 10.1142/S1793830913600045
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Mathematics, Algorithms and Applications
MetadataShow full item record
Abstract (EN)The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Π, 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 Π 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 Pk-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.
Subjects / Keywordsreoptimization
Showing items related by title and author.