Introduction An FPT algorithm

Introduction An FPT algorithm

36

pages

English

Documents

Écrit par
Nicolas Bousquet

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 en t'inscrivant gratuitement

Découvre YouScribe en t'inscrivant gratuitement

36

pages

English

Ebook

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

35

Langue

English

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

Publié par

Nombre de lectures

35

Langue

English

Bousquet Parameterized complexity Instance

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 diﬀerent proofs

1

2

Mcutiulti

TalgorittionAnFPnIrtdocuexplomdczeritemearaPnoisulcnoCmhuctluittiMynIeretwkretemarapaotnoisenerwhn,<<hkitocbmteehnonﬁtsC?losilexporiainathtllorpelecrA)elblnanteiembleﬁsdtfehnitshtsezioeorem(Couance.TheraFedihtluitTPM.edbyerizreewthetigoLredrtemarapcdinaMohedOoneccSticuPTsF

FPT A problem parameterized bykisFPT(Fixed Parameter Tractable) iﬀ there is an algorithm which runs in timePoly(n)∙f(k) for an instance of sizenand of parameterk.

FPT

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

© 2010-2024 YouScribe

Livre audio en ligne - Développement personnel Livre en ligne Tout le catalogue Tous les Intérêts