On linear and circular structure of (claw, net)-free graphs
type: Item
instance of: scholarly article
title: On linear and circular structure of (claw, net)-free graphs
zbMATH Open document ID: 1032.05095
DOI: 10.1016/S0166-218X(02)00571-1
author: Andreas Brandstädt
author: Feodor F. Dragan
published in: Discrete Applied Mathematics
publication date: 2003-09-09T00:00:00Z
review text: 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.
reviewed by: Bert Randerath
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1977898
zbMATH Keywords: (claw, net)-free graphs
zbMATH Keywords: linear structure
zbMATH Keywords: circular structure
zbMATH Keywords: dominating cycle
zbMATH Keywords: independent domination
zbMATH Keywords: stability number
zbMATH Keywords: linear-time algorithm
MaRDI profile type: Publication
cites work: On domination and independent domination numbers of a graph
cites work: Partial orders of dimension 2
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: A Linear Time Algorithm for Deciding Interval Graph Isomorphism
cites work: Linear time algorithms for Hamiltonian problems on (claw, net)-free graphs
cites work: LexBFS-orderings and powers of chordal graphs
cites work: Graph Classes: A Survey
cites work: Independent Sets in Asteroidal Triple-Free Graphs
cites work: Q3797233
cites work: A linear time algorithm to compute a dominating path in an AT-free graph
cites work: Asteroidal Triple-Free Graphs
cites work: Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
cites work: Trapezoid graphs and their coloring
cites work: Q4342632
cites work: Q3918148
cites work: Permutation Graphs and Transitive Graphs
cites work: Q3328583
cites work: Tolerance graphs
cites work: The struction of a graph: Application to CN-free graphs
cites work: On claw-free asteroidal triple-free graphs
cites work: On the semi-perfect elimination
cites work: Domination on Cocomparability Graphs
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Hamiltonicity in claw-free graphs
cites work: Characterizing circular-arc graphs
cites work: Matrix characterizations of circular-arc graphs
cites work: Edge Dominating Sets in Graphs
full work available at URL: s0166-218x(02)00571-1
OpenAlex ID: W1983733602
description: scientific article; zbMATH DE number 1977898