The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Π, an optimal solution OPT for Π 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 in order 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 in order to study weighted versions of several representatives of a broad class of problems known in the literature as maximum induced hereditary subgraph problems. The main problems studied are max independent set, max k-colorable subgraph and max split subgraph under vertex insertions and deletions.

Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems / Boria, Nicolas; Jérôme, Monnot; Paschos, Vangelis T. h.. - 7256:(2012), pp. 73-84. (Intervento presentato al convegno 0th Latin American Symposium tenutosi a Arequipa (Peru) nel April 16-20, 2012) [10.1007/978-3-642-29344-3_7].

Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems

BORIA, NICOLAS;
2012

Abstract

The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Π, an optimal solution OPT for Π 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 in order 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 in order to study weighted versions of several representatives of a broad class of problems known in the literature as maximum induced hereditary subgraph problems. The main problems studied are max independent set, max k-colorable subgraph and max split subgraph under vertex insertions and deletions.
2012
9783642293436
9783642293443
File in questo prodotto:
File Dimensione Formato  
reopt-hered-LATIN.pdf

accesso aperto

Tipologia: 1. Preprint / submitted version [pre- review]
Licenza: PUBBLICO - Tutti i diritti riservati
Dimensione 249 kB
Formato Adobe PDF
249 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2500157
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo