P-4-LADEN GRAPHS - A NEW CLASS OF BRITTLE GRAPHS

Authors
GIAKOUMAKIS V
Citation
V. Giakoumakis, P-4-LADEN GRAPHS - A NEW CLASS OF BRITTLE GRAPHS, Information processing letters, 60(1), 1996, pp. 29-36
Citations number
16
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
60
Issue
1
Year of publication
1996
Pages
29 - 36
Database
ISI
SICI code
0020-0190(1996)60:1<29:PG-ANC>2.0.ZU;2-0
Abstract
We present a new family of graphs, the family of P-4-laden graphs stri ctly containing the class of P-4-lite graphs introduced in (Jamison an d Olariu, 1989). We first show that P-4-laden graphs are brittle and n ext, using modular decomposition we present for this class of graphs a linear recognition algorithm as well as linear algorithms for classic al optimization problems.