In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with α(G)≤3α(G)≤3 in time O(|E|log|V|). More precisely, in time O(|E|) we check whether α(G)≤3or produce a stable set with cardinality at least 4; moreover, if α(G)≤3 we produce in time O(|E|log|V|) a maximum weight stable set of G. This improves the bound of O(|E||V|) due to Faenza, Oriolo and Stauffer.
An O(mlogn) algorithm for the weighted stable set problem in claw-free graphs with α(G)≤3 / Nobili, Paolo; Sassano, Antonio. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - ELETTRONICO. - 164:1-2(2017), pp. 157-165. [10.1007/s10107-016-1080-9]
An O(mlogn) algorithm for the weighted stable set problem in claw-free graphs with α(G)≤3
SASSANO, Antonio
2017
Abstract
In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with α(G)≤3α(G)≤3 in time O(|E|log|V|). More precisely, in time O(|E|) we check whether α(G)≤3or produce a stable set with cardinality at least 4; moreover, if α(G)≤3 we produce in time O(|E|log|V|) a maximum weight stable set of G. This improves the bound of O(|E||V|) due to Faenza, Oriolo and Stauffer.| File | Dimensione | Formato | |
|---|---|---|---|
|
Nobili_An-O(mlog-n)_2017.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
412.67 kB
Formato
Adobe PDF
|
412.67 kB | Adobe PDF | Contatta l'autore |
|
Nobili_preprint_An-O(mlog-n)_2017.pdf
accesso aperto
Note: DOI 10.1007/s10107-016-1080-9
Tipologia:
Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
102.44 kB
Formato
Adobe PDF
|
102.44 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
