Introduction A polynomial time algorithm

Pim Van 'T Hof

Description

Introduction A polynomial-time algorithm Conclusions Finding induced paths of given parity in claw-free graphs Pim van 't Hof joint work with Marcin Kaminski and Daniel Paulusma WG 2009, 24–26 June 2009 Pim van 't Hof Finding induced paths of given parity in claw-free graphs

• time algorithm


• problem can


• pim van


• linear time


• claw-free graphs


• finding induced

Sujets

• Kaminski
• Time complexity

Informations

• Publié par: pefav
• Nombre de lectures: 10
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Introduction A polynomial-time algorithm Conclusions

Finding

joint

work

paths of given -free graphs

induced in claw

with

Pim

Marcin

WG

2009,

van

’t

Hof

Kamin´ski

24–26

Pim van ’t Hof

and

June

parity

Dani¨el

2009

Paulusma

Finding induced paths of given parity in claw-free graphs

Finding

paths

Introduction A polynomial-time algorithm Conclusions of given parity

Pim van ’t Hof

Finding induced paths of given parity in claw-free graphs

Finding

paths

Introduction A polynomial-time algorithm Conclusions of given parity

Pim van t Hof ’

Finding induced paths of given parity in claw-free graphs

Finding

paths

Introduction A polynomial-time algorithm Conclusions of given parity

Pim van t Hof ’

Finding induced paths of given parity in claw-free graphs

Introduction A polynomial-time algorithm Conclusions Finding paths of given parity

Odd Path Instance:A graphGand two verticessandt. Question:DoesGhave an odd path fromstot?

Even Path Instance:A graphGand two verticessandt. Question:DoesGhave an even path fromstot?

Pim van ’t Hof

Finding induced paths of given parity in claw-free graphs

Introduction A polynomial-time algorithm Conclusions Finding paths of given parity

is easy

Odd Path Instance:A graphGand two verticessandt. Question:DoesGhave an odd path fromstot?

Even Path Instance:A graphGand two verticessandt. Question:DoesGhave an even path fromstot?

Theorem (LaPaugh & Papadimitriou, 1984) Both theOdd Pathproblem and theEven Pathproblem can be solved in linear time.

Pim van ’t Hof

Finding induced paths of given parity in claw-free graphs

Finding

Introduction A polynomial-time algorithm Conclusions induced paths of given

Pim van ’t Hof

parity

Finding induced paths of given parity in claw-free graphs

Finding

Introduction A polynomial-time algorithm Conclusions induced paths of given

Pim van ’t Hof

parity

Finding induced paths of given parity in claw-free graphs

Finding

Introduction A polynomial-time algorithm Conclusions induced paths of given

Pim van ’t Hof

parity

Finding induced paths of given parity in claw-free graphs

Finding

Introduction A polynomial-time algorithm Conclusions induced paths of given

Pim van ’t Hof

parity

Finding induced paths of given parity in claw-free graphs