Linear time algorithms or hamiltonian problems on (claw, net)-free graphs

Citation
A. Brandstadt et al., Linear time algorithms or hamiltonian problems on (claw, net)-free graphs, SIAM J COMP, 30(5), 2000, pp. 1662-1677
Citations number
28
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
30
Issue
5
Year of publication
2000
Pages
1662 - 1677
Database
ISI
SICI code
0097-5397(2000)30:5<1662:LTAOHP>2.0.ZU;2-K
Abstract
We prove that claw-free graphs, containing an induced dominating path, have a Hamiltonian path, and that 2-connected claw-free graphs, containing an i nduced doubly dominating cycle or a pair of vertices such that there exist two internally disjoint induced dominating paths connecting them, have a Ha miltonian cycle. As a consequence, we obtain linear time algorithms for bot h problems if the input is restricted to (claw, net)-free graphs. These gra phs enjoy those interesting structural properties.