WEIGHTED PARAMETERS IN (P-5,(P-5)OVER-BAR)-FREE GRAPHS

Authors
GIAKOUMAKIS V RUSU I
Citation
V. Giakoumakis et I. Rusu, WEIGHTED PARAMETERS IN (P-5,(P-5)OVER-BAR)-FREE GRAPHS, Discrete applied mathematics, 80(2-3), 1997, pp. 255-261
Citations number
9
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
80
Issue
2-3
Year of publication
1997
Pages
255 - 261
Database
ISI
SICI code
Abstract
We use the modular decomposition to give O(n(m + n)) algorithms for fi nding a maximum weighted clique (respectively stable set) and an appro ximate weighted colouring (respectively partition into cliques) in a ( P-5,(P-5) over bar)-free graph. As a by-product, we obtain an O(mfn) a lgorithm for finding a minimum weighted transversal of the Cs in a (P- 5,(P-5) over bar)-free graph.