On linear and circular structure of (claw, net)-free graphs (Q1406025)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On linear and circular structure of (claw, net)-free graphs |
scientific article |
Statements
On linear and circular structure of (claw, net)-free graphs (English)
0 references
9 September 2003
0 references
By exploiting structural properties of (claw, net)-free graphs, the authors are able to obtain efficient algorithms for the domination, independent domination, and the independent set problem on this class. A structural analysis of the family of (claw, net)-free graphs reveals the existence of an induced doubly dominating cycle or a dominating pair. Linear-time algorithms using LexBFS are presented for finding in a (claw, net)-free graph either a dominating pair or an induced doubly dominating cycle. In summary, the authors provide another beautiful example for studying special graph classes.
0 references
(claw, net)-free graphs
0 references
linear structure
0 references
circular structure
0 references
dominating cycle
0 references
independent domination
0 references
stability number
0 references
linear-time algorithm
0 references
0 references
