A note on vertex orders for stability number

Authors
Mahadev, NVR Reed, BA
Citation
Nvr. Mahadev et Ba. Reed, A note on vertex orders for stability number, J GRAPH TH, 30(2), 1999, pp. 113-120
Citations number
10
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF GRAPH THEORY
ISSN journal
03649024 → ACNP
Volume
30
Issue
2
Year of publication
1999
Pages
113 - 120
Database
ISI
SICI code
0364-9024(199902)30:2<113:ANOVOF>2.0.ZU;2-I
Abstract
We investigate vertex orders that can be used to obtain maximum stable sets by a simple greedy algorithm in polynomial time in some classes of graphs. We characterize a class of graphs for which the stability number can be ob tained by a simple greedy algorithm. This class properly contains previousl y known classes of graphs for which the stability number can be computed in polynomial time. (C) 1999 John Wiley & Sons, Inc.