𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Andreas Brandstädt

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
437 KB
Volume
138
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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 consists of four vertices a; b; c; d such that a; b; c form an induced path with edges ab; bc, and vertex d is adjacent to a; b and c). The structure and bounded clique width of this graph class allows to solve several algorithmic problems on this class in linear time, among them the problems Maximum Weight Stable Set (MWS), Maximum Weight Clique, Domination, Steiner Tree and in general every algorithmic problem which is, roughly speaking, expressible in a certain kind of Monadic Second-Order Logic using quantiÿcation only over vertex but not over edge set predicates. This improves previous results on (P5,diamond)-free graphs in several ways: We give a complete structure description of prime (P5,diamond)-free graphs, we do not only solve the MWS problem on this class, we achieve linear time algorithms (instead of a recent time bound O(nm)), and we can do all this on a larger graph class containing (P5,diamond)-free graphs which admits linear time recognition.

📜 SIMILAR VOLUMES

Structure and stability number of chair-
Structure and stability number of chair-, co-P- and gem-free graphs revisited
✍ Andreas Brandstädt; Hoàng-Oanh Le; Jean-Marie Vanherpe 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 110 KB

The P 4 is the induced path with vertices a, b, c, d and edges ab, bc, cd. The chair (co-P, gem) has a fifth vertex adjacent to b (a and b, a, b, c and d, respectively). We give a complete structure description of prime chair-, co-P-and gem-free graphs which implies bounded clique width for this gra

On the structure and stability number of
On the structure and stability number of P5- and co-chair-free graphs
✍ Andreas Brandstädt; Raffaele Mosca 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 336 KB

We give a O(nm) time algorithm for the maximum weight stable set (MWS) problem on P5-and co-chair-free graphs without recognizing whether the (arbitrary) input graph is P5and co-chair-free. This algorithm is based on the fact that prime P5-and co-chair-free graphs containing 2K2 are matched co-bipar