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.

Autore Pugliese

• Nobili Paolo

Tutti gli autori

• P. Nobili , A. Sassano

Titolo volume/Rivista

MATHEMATICAL PROGRAMMING

Anno di pubblicazione

2017

ISSN

0025-5610

ISBN

Non Disponibile

Numero di citazioni Wos

Nessuna citazione

Ultimo Aggiornamento Citazioni

Non Disponibile

Numero di citazioni Scopus

Non Disponibile

Ultimo Aggiornamento Citazioni

Non Disponibile

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile