资源描述：
《Invitation to fixed-parameter algorithms》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Habilitationthesis,UniversittTubingen,2002¨RolfNiedermeierInvitationtoFixed-ParameterAlgorithmsOctober23,2002Habilitationthesis,UniversittTubingen,2002¨PrefaceThisworkisbasedonmyoccupationwithparameterizedcomplexityandfixed-parameteralgorithmswhichbeganmorethanfouryearsago.Duringthattime,mythreemosti
2、mportantresearchpartnerswereJochenAlber,JensGramm,andPeterRossmanith.Nearlyallofmyworkintheseyearsemergedfromresearchwithoneoranotherofthesethreepeople.Ialsoprof-itedfromjointresearchwithHansL.Bodlaender,MichaelR.Fellows,Hen-ningFernau,JiongGuo,andTonKlokswhichledtosomefindingsinthisproject.Clearly,I
3、owesincerethankstoallofthementionedpeopleandmanymoreunnamedones.MyresearchwasgenerouslysupportedbytheDeutscheForschungsge-meinschaft(DFG)throughtheprojects“ParameterizedComplexityandEx-actAlgorithms(PEAL)”,NI369/1-1,2,and“OptimalSolutionsforHardProblemsfromComputationalBiology(OPAL)”,NI369/2-1,which
4、paidfortheworkofJochenAlber,JensGramm,andseveralstudents.Inthesubsequenttext,whichismainlybasedonownresearchmaterial,Ialwaysgivetheconnectionstothecorrespondingpublications.Inordertokeepthepresentationwithinreasonablesize,fromtimetotime(awkward)technicaldetailsandproofsareomitted—allofthemcanbefound
5、inthecitedliterature.T¨ubingen,September2002RolfNiedermeierHabilitationthesis,UniversittTubingen,2002¨Habilitationthesis,UniversittTubingen,2002¨Contents1.Foundations..............................................11.1KeeptheParameterFixed...............................11.2PreliminariesandAgreements..
6、..........................21.3ParameterizedComplexity—aBriefOverview..............61.3.1BasicTheory....................................61.3.2InterpretingFixed-ParameterTractability...........91.4VertexCover–anIllustrativeExample.................111.4.1Parameterize....................................
7、121.4.2Specialize.......................................131.4.3Generalize.......................................141.4.4CountorEnumerate..............................151.4.5Lower-Bound.................
