✦ LIBER ✦

Weighted parameters in (P5, P5)-free graphs

✍ Scribed by Vassilis Giakoumakis; Irena Rusu

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 488 KB
Volume: 80
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(97)00093-0

No coin nor oath required. For personal study only.

✦ Synopsis

We use the modular decomposition to give O(n(m + n)) algorithms for finding a maximum weighted clique (respectively stable set) and an approximate weighted colouring (respectively partition into cliques) in a (&,E)-free graph. As a by-product, we obtain an O(m+n) algorithm for finding a minimum weighted transversal of the CS in a (Ps,&)-free graph.

📜 SIMILAR VOLUMES

Dominating cliques in P5-free graphs

✍ G. Bacsó; Zs. Tuza 📂 Article 📅 1990 🏛 Springer Netherlands 🌐 English ⚖ 372 KB

A decomposition for a class of (P5,P̄5)-

A decomposition for a class of (P5,P̄5)-free graphs

✍ J.L. Fouquet 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 598 KB

Fouquet, J.L., A decomposition for a class of (P,, P,)-free graphs, Discrete Mathematics 121 (1993) 75-83. We give a decomposition for a subclass of (P5, P, )-free graphs, leading to an 0(n3) algorithm for the recognition of this class of graphs.

On α-redundant vertices in P5-free graph

On α-redundant vertices in P5-free graphs

✍ Andreas Brandstädt; Hoàng-Oanh Le; Van Bang Le 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 73 KB

Some results on maximum stable sets in c

Some results on maximum stable sets in certain P5-free graphs

✍ Raffaele Mosca 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 149 KB

(P5,diamond)-free graphs revisited: stru

(P5,diamond)-free graphs revisited: structure and linear time optimization

✍ Andreas Brandstädt 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 437 KB

Using the concept of prime graphs and modular decomposition of graphs, we give a complete structure description of (P5,diamond)-free graphs implying that these graphs have bounded clique width (the P5 is the induced path with ÿve vertices a; b; c; d; e and four edges ab; bc; cd; de, and the diamond

P5-free augmenting graphs and the maximu

P5-free augmenting graphs and the maximum stable set problem

✍ Michael U. Gerber; Alain Hertz; David Schindl 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 174 KB

The complexity status of the maximum stable set problem in the class of P5-free graphs is unknown. In this paper, we ÿrst propose a characterization of all connected P5-free augmenting graphs. We then use this characterization to detect families of subclasses of P5-free graphs where the maximum stab