Skip to main content
Article
Linear Time Algorithms or Hamiltonian Problems on (Claw, Net)-Free Graphs
SIAM Journal on Computing
  • Andreas Brandstädt, Universität Rostock
  • Feodor F Dragan, Kent State University - Kent Campus
  • Ekkehard Köhler, Technische Universität Berlin
Publication Date
1-1-2000
Document Type
Article
Disciplines
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 induced doubly dominating cycle or a pair of vertices such that there exist two internally disjoint induced dominating paths connecting them, have a Hamiltonian cycle. As a consequence, we obtain linear time algorithms for both problems if the input is restricted to (claw,net)-free graphs. These graphs enjoy those interesting structural properties.
Comments

Copyright 2000 Society for Industrial and Applied Mathematics.

Citation Information
Andreas Brandstädt, Feodor F Dragan and Ekkehard Köhler. "Linear Time Algorithms or Hamiltonian Problems on (Claw, Net)-Free Graphs" SIAM Journal on Computing Vol. 30 Iss. 5 (2000) p. 1662 - 1677
Available at: http://works.bepress.com/feodor_dragan/2/