𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem

✍ Scribed by Andreas Brandstädt; Chính T. Hoàng

Book ID
108281366
Publisher
Elsevier Science
Year
2007
Tongue
English
Weight
427 KB
Volume
389
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A generalization of chordal graphs and t
A generalization of chordal graphs and the maximum clique problem
✍ Assef Chmeiss; Philippe Jégou 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 584 KB

A graph is chordal or triangulated if it has no chordless cycle with four or more vertices. Chordal graphs are well known for their combinatorial and algorithmic properties. Here we introduce a generalization of chordal graphs, namely CSGk graphs. Informally, a CSG' graph is a complete graph, and fo

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