Fast exact algorithms for hamiltonicity in claw free graphs

Fedor Fomin2

Description

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

Sujets

• Hamiltonian path
• Travelling salesman problem
• Planar graph

Informations

• Publié par: pefav
• Nombre de lectures: 14
• Langue: English

Extrait

Fast

exact algorithms for hamiltonicity in claw-free graphs

1

Hajo Broersma Fedor Fomin 2 Pim van ’t Hof 1 Dani¨elPaulusma 1

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

K 1,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 ∗ (2 n )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.