Fast exact algorithms for hamiltonicity in claw free graphs

Fast exact algorithms for hamiltonicity in claw free graphs

31

pages

English

Documents

Écrit par
Fedor Fomin2

Publié par
pefav

Lire un extrait

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe et accède à tout notre catalogue !

Découvre YouScribe et accède à tout notre catalogue !

31

pages

English

Documents

Lire un extrait

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

Nombre de lectures

14

Langue

English

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

Publié par

Langue

English

Hamiltonian path Travelling salesman problem Planar graph

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 ﬁnite, 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:ﬁnd 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.