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
Type
Article accepté pour publication ou publiéDate
2013Journal name
Discrete Mathematics, Algorithms and ApplicationsVolume
05Number
02Pages
n°1360004
Publication identifier
Metadata
Show full item recordAbstract (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 / Keywords
reoptimizationRelated items
Showing items related by title and author.
-
Boria, Nicolas; Monnot, Jérôme; Paschos, Vangelis (2012) Communication / Conférence
-
Boria, Nicolas; Paschos, Vangelis; Monnot, Jérôme (2013) Article accepté pour publication ou publié
-
Boria, Nicolas; Della Croce, Federico; Paschos, Vangelis (2014) Communication / Conférence
-
Monnot, Jérôme; Paschos, Vangelis; Toulouse, S. (2003) Article accepté pour publication ou publié
-
Boria, Nicolas; Gourvès, Laurent; Paschos, Vangelis; Monnot, Jérôme (2021) Communication / Conférence