1. Open Access Kent State
  2. Linear Time Algorithms or Hamiltonian Problems on (Claw, Net)-Free Graphs
Author(s)
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.
Format
Article
Publication Date
2000-01-01
Publication Title
SIAM Journal on Computing
Volume
30
Issue
5
First Page
1662
Last Page
1677
Subject
Community
Department of Computer Science
Comments

Copyright 2000 Society for Industrial and Applied Mathematics.
Permalink https://oaks.kent.edu/cspubs/4
Brandstädt, A., Dragan, F., & Köhler, E. (2000). Linear Time Algorithms or Hamiltonian Problems on (Claw, Net)-Free Graphs. SIAM Journal on Computing. https://oaks.kent.edu/node/1330
Brandstädt, Andreas, Feodor Dragan, and Ekkehard Köhler. 2000. “Linear Time Algorithms or Hamiltonian Problems on (Claw, Net)-Free Graphs”. SIAM Journal on Computing. https://oaks.kent.edu/node/1330.
Brandstädt, A., F. Dragan, and E. Köhler. Linear Time Algorithms or Hamiltonian Problems on (Claw, Net)-Free Graphs. SIAM Journal on Computing, 1 Jan. 2000, https://oaks.kent.edu/node/1330.