Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems

Tipo di pubblicazione: Articolo in atti di convegno
Tipologia MIUR: Contributo in Atti di Convegno (Proceeding) > Contributo in atti di convegno
Titolo: Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems
Autori: Nicolas Boria; Jérôme Monnot; Vangelis Th. Paschos
Autori di ateneo:
Intervallo pagine: pp. 73-84
Titolo del periodico: LECTURE NOTES IN COMPUTER SCIENCE
Editore: Springer
ISBN: 9783642293436
ISSN: 0302-9743
Volume: 7256
Titolo del convegno: 0th Latin American Symposium
Luogo dell'evento: Arequipa (Peru)
Data dell'evento: April 16-20, 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
Data: 2012
Status: Pubblicato
Lingua della pubblicazione:
Parole chiave:
Dipartimenti (originale): DAUIN - Dipartimento di Automatica Informatica
Dipartimenti: NON SPECIFICATO
URL correlate:
    Area disciplinare:
    Data di deposito: 12 Lug 2012 12:51
    Data ultima modifica (IRIS): 09 Mag 2016 14:46:43
    Data inserimento (PORTO): 26 Ago 2016 04:56
    Numero Identificativo (DOI): 10.1007/978-3-642-29344-3_7
    Permalink: http://porto.polito.it/id/eprint/2500157
    Link resolver URL: Link resolver link
    Citazioni:

    Il campo presenta il numero di citazioni presenti sulle banche dati Scopus e Web of Science e permette di accedere ai relativi record. Visualizza inoltre il link al record presente su Google Scholar.

    Possono verificarsi discrepanze rispetto ai dati presenti sulle banche dati per i seguenti motivi:

    • Differenze tra i dati riportati su IRIS e quelli presenti nelle banche dati.
    • Il numero di citazioni riportate su PORTO viene estratto mensilmente. Il dato citazionale presente sulle singole banche dati è aggiornato in tempo reale
    • Il numero di citazioni per WoS viene calcolato sulla base delle collezioni in abbonamento (Science citation index Expanded e Conference Proceedings Citation Index)

    Per informazioni o segnalazioni contattare scrivia/porto

    +
    -

    Allegati

    [img] PDF (2500157.pdf) - Postprint
    Accesso al documento: Non visibile (accessibile solo al proprietario del dato)
    Licenza: Non pubblico - Accesso privato / Ristretto.

    Download (250Kb (256481 bytes)) | Spedisci una richiesta all'autore per una copia del documento
    [img]
    Preview
    PDF (reopt_hered_LATIN.pdf) - Preprint
    Accesso al documento: Visibile (Ad accesso aperto)
    Licenza: Pubblico - Tutti i diritti riservati.

    Download (248Kb (254972 bytes)) | Preview

    Azioni (richiesto il login)

    Visualizza il documento (riservato amministratori) Visualizza il documento (riservato amministratori)

    Statistiche sul Download degli allegati

    Altre statistiche su questa pubblicazione...