Computing Maximum Stable Set for Distance-Hereditary Graphs

Olivier Cogis; Eric Thierry

doi:10.1016/j.disopt.2005.03.004

Back

Computing Maximum Stable Set for Distance-Hereditary Graphs

Journal article

Open access

Peer reviewed

Computing Maximum Stable Set for Distance-Hereditary Graphs

Olivier Cogis and Eric Thierry

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

2005

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

Abstract

Greedy scheme

Distance-hereditary graph

Combinatorial optimization

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

See more details

Details

Title: Computing Maximum Stable Set 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: 9938703109311
Academic Unit: Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
Language: English
Resource Type: Journal article
Local Fields: lirmm-00105342