CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishIn this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with α(G)≤3 in time O(|E|log|V|). More precisely, in time O(|E|) we check whether α(G)≤3 or 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.
| Titolo: | An O(mlogn) algorithm for the weighted stable set problem in claw-free graphs with α(G)≤3 |
| Autori: | |
| Data di pubblicazione: | 2017 |
| Rivista: | |
| 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 in time O(|E|log|V|). More precisely, in time O(|E|) we check whether α(G)≤3 or 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. |
| Handle: | http://hdl.handle.net/11587/417578 |
| Appare nelle tipologie: | Articolo pubblicato su Rivista |
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
Copyright © 2020