Computing maximum stable sets for distance-hereditary graphs

Olivier Cogis; Eric Thierry

doi:10.1016/j.disopt.2005.03.004

Back

Computing maximum stable sets for distance-hereditary graphs

Journal article

Open access

Peer reviewed

Computing maximum stable sets for distance-hereditary graphs

Olivier Cogis and Eric Thierry

Discrete Optimization, Vol.2(2), pp.185-188

06/2005

DOI: https://doi.org/10.1016/j.disopt.2005.03.004

Abstract

Distance-hereditary graph

Combinatorial optimization

Greedy scheme

In this note, we provide a new and simple algorithm to compute maximum stable sets for distance-hereditary graphs. It corrects the algorithm presented by Hammer and Maffray [Discrete Appl. Math. 27 (1990) 85–99], but remains within the general greedy scheme that was suggested by Hammer and Maffray (1990).

Files and links (2)

url

Find in HALView

url

https://doi.org/10.1016/j.disopt.2005.03.004View

Published (Version of record) Open

Metrics

1 Record Views

Details

Title: Computing maximum stable sets for distance-hereditary graphs
Creators - without role: Olivier Cogis - Algorithmes et Performance des Réseaux
Eric Thierry - Laboratoire de l'Informatique du Parallélisme
Publication Details: Discrete Optimization, Vol.2(2), pp.185-188
Identifiers: 9941594809311
Academic Unit: Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
Language: English
Resource Type: Journal article
Local Fields: hal-04659469