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

Introduction A polynomial time algorithm

De
104 pages
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


Voir plus Voir moins
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