On algorithms for ( P 5 ,gem)-free graphs

A graph is ( P 5 ,gem)-free, when it does not contain P 5 (an induced path with five vertices) or a gem (a graph formed by making an universal vertex adjacent to each of the four vertices of the induced path P 4 ) as an induced subgraph. We present O ( n 2 ) time recognition algorithms for chordal g...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2005-01, Vol.349 (1), p.2-21
Main Authors: Bodlaender, Hans L., Brandstädt, Andreas, Kratsch, Dieter, Rao, Michaël, Spinrad, Jeremy
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Clique
Clique cover
Coloring
Combinatorics
Combinatorics. Ordered structures
Computer Science
Computer science
control theory
systems
Data Structures and Algorithms
Exact sciences and technology
formula omitted
Gem)-free graphs
Graph theory
Independent set
Mathematics
Modular decomposition
Recognition algorithms
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A graph is ( P 5 ,gem)-free, when it does not contain P 5 (an induced path with five vertices) or a gem (a graph formed by making an universal vertex adjacent to each of the four vertices of the induced path P 4 ) as an induced subgraph. We present O ( n 2 ) time recognition algorithms for chordal gem-free graphs and for ( P 5 ,gem)-free graphs. Using a characterization of ( P 5 ,gem)-free graphs by their prime graphs with respect to modular decomposition and their modular decomposition trees [A. Brandstädt, D. Kratsch, On the structure of ( P 5 ,gem)-free graphs, Discrete Appl. Math. 145 (2005), 155–166], we give linear time algorithms for the following NP-complete problems on ( P 5 ,gem)-free graphs: Minimum Coloring; Maximum Weight Stable Set; Maximum Weight Clique; and Minimum Clique Cover.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2005.09.026