Exact algorithms for dominating clique problems

Il contenuto (Full text) non è disponibile all'interno di questo archivio. Spedisci una richiesta all'autore per una copia del documento
Tipo di pubblicazione: Articolo in atti di convegno
Tipologia MIUR: Contributo in Atti di Convegno (Proceeding) > Contributo in atti di convegno
Titolo: Exact algorithms for dominating clique problems
Autori: N. Bourgeois; Della Croce Di Dojola F.; B. Escoffier; V.T. Paschos
Autori di ateneo:
Intervallo pagine: pp. 4-13
Titolo del periodico: LECTURE NOTES IN COMPUTER SCIENCE
Tipo di referee: Tipo non specificato
Editore: Springer
ISBN: 9783642106316
ISSN: 0302-9743
Volume: 5878
Titolo del convegno: 20th International Symposium, ISAAC 2009
Luogo dell'evento: Honolulu, Hawaii (USA)
Data dell'evento: December 16-18, 2009
Abstract: We handle in this paper three dominating clique problems, namely, the decision problem itself when one asks if there exists a dominating clique in a graph G and two optimization versions where one asks for a maximum- and a minimum-size dominating clique, if any. For the three problems we propose optimal algorithms with provably worst-case upper bounds improving existing ones by (D. Kratsch and M. Liedloff, An exact algorithm for the minimum dominating clique problem, Theoretical Computer Science 385(1-3), pp. 226-240, 2007). We then settle all the three problems in sparse and dense graphs also providing improved upper running time bounds
Data: 2009
Status: Pubblicato
Lingua della pubblicazione: Inglese
Parole chiave:
Dipartimenti (originale): DAUIN - Dipartimento di Automatica Informatica
Dipartimenti: DAUIN - Dipartimento di Automatica e Informatica
URL correlate:
    Area disciplinare: Area 01 - Scienze matematiche e informatiche > RICERCA OPERATIVA
    Data di deposito: 14 Gen 2010 18:00
    Data ultima modifica (IRIS): 16 Set 2016 15:27:48
    Data inserimento (PORTO): 18 Set 2016 04:46
    Numero Identificativo (DOI): 10.1007/978-3-642-10631-6_3
    Permalink: http://porto.polito.it/id/eprint/2302842
    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

    +
    -

    Azioni (richiesto il login)

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