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 An FPT algorithm

De
36 pages
Introduction An FPT algorithm Conclusion Multicut is FPT Nicolas Bousquet Jean Daligault Daniel Marx Igor Razgon Stephan Thomasse STOC 2011 Multicut is FPT

  • parameterized complexity

  • instance

  • fpt algorithm

  • time poly

  • instance left cuts

  • fpt

  • fixed parameter


Voir plus Voir moins
IntroductionAnFTPlaogirhtCmnolciousntluMT
Marx
Igor
Nicolas
BousquetnDalJealtD´igaulnaei RazgonSte´phanThomasse´
STOC 2011
Multicut is FPT
citusiPF
tiucAnonInodtroCcntimhglroPFaTterirameonPalusiluMytixelpmocdeztcuti
3
Introduction Parameterized complexity Multicut
Conclusion
FsTP
An FPT algorithm Reducing the instance Left cuts Two different proofs
1
2
Mcutiulti
TalgorittionAnFPnIrtdocuexplomdczeritemearaPnoisulcnoCmhuctluittiMynIeretwkretemarapaotnoisenerwhn,<<hkitocbmteehnontsC?losilexporiainathtllorpelecrA)elblnanteiemblesdtfehnitshtsezioeorem(Couance.TheraFedihtluitTPM.edbyerizreewthetigoLredrtemarapcdinaMohedOoneccSticuPTsF
FPT A problem parameterized bykisFPT(Fixed Parameter Tractable) iff there is an algorithm which runs in timePoly(n)f(k) for an instance of sizenand of parameterk.
FPT
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin