On linear and circular structure of (claw, net)-free graphs
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.
scientific article; zbMATH DE number 1977898
scientific article