//img.uscri.be/pth/7b36fd81dad7b066df3222eff3d93432a7c4710b
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Fast exact algorithms for hamiltonicity in claw free graphs

De
31 pages
Fast exact algorithms for hamiltonicity in claw-free graphs Hajo Broersma1 Fedor Fomin2 Pim van 't Hof1 Daniel Paulusma1 Durham University1 University of Bergen2 WG 2009

  • regular claw-free

  • hamiltonian cycle

  • exact algorithms

  • salesman problem

  • o?-notation suppresses

  • claw-free graphs

  • planar graphs

  • free graph

  • fast exact


Voir plus Voir moins
Fast
exact algorithms for hamiltonicity in claw-free graphs
1
Hajo Broersma Fedor Fomin2 Pim van ’t Hof1 Dani¨elPaulusma1
Durham University
1
University of Bergen
WG 2009
2
Introduction
G= (V,E) is finite, undirected graph, no loops, no multiple edges.
Gisclaw-freeifGdoes not contain an inducedclaw, which is a
K1,3= ({u,a,b,c},{ua,ub,uc}).
Goal:find ahamiltonian cycleof a claw-free graph.
Theorem (Li, Corneil & Mendelsohn, 2000)
Deciding if a graph has a hamiltonian cycle is NP-complete even for the class of 3-connected 3-regular claw-free planar graphs.
We aim for anexactalgorithm.
Theorem (Karp, 1982)
Known Results
Hamiltonian Cyclecan be solved using O(2n)time and polynomial space for any n-vertex graph.
Here,O-notation suppresses factors of polynomial order.
Major open problem:
CanHamiltonian C
CanHamiltonian Cyclebe solved in O(αn)time forα <2?
Even unknown if polynomial space is dropped.