Matching和packing問題的參數(shù)算法研究.pdf

1、中南大學(xué)碩士學(xué)位論文Matching和packing問題的參數(shù)算法研究姓名：寧丹申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)指導(dǎo)教師：王建新20070401ABSTRACTMatchingandpackingproblemshaveformedanimportantclassofNP—hardproblems3DmatchingproblemandP2packingproblemaretypicalmatchingandpackingprob

2、lemrespectivelyIntheframeworkoftheparameterizedcomplexitytherehasbeenaremarkablelineofresearchinthestudyofparameterizedalgorithmforthe3DmatchingproblemandP2一packingproblemInthispaperwemainlystudyonthekernelizationandpara

3、meterizedalgorithmforthe3DmatchingproblemandP2packingproblemWefirstlyintroducekemelization，anddescribethekernelizationalgorithmofvertexcoverproblemand3DmatchingproblemAtthesametime，wedevelopaimprovedkernelizationalgorith

4、m，SOthatwecanreducethekernelofsizetoatmost6礦12k26kForthe3Dmatchingproblem，wefurtherobservesymbolsrelationshipbetweenakmatchingandakl—matchingoftheinstanceBasedontheobservationandanewColorCodingtheoryofJChen，wepresentadet

5、erministicparameterizedalgorithmofrunningtimeO’(3423勺，andourdeterministicalgorithmsignificantlyimprovesthepresentbestdeterministicalgorithmofrunningtime0。(163勺FortheP2一packingproblem，weprovidefurthertheoreticalstudyonthe

6、structuresoftheproblem，andpresentanewkemelizationalgorithmByusingthenewkernelizationalgorithm，wecarlobtainakernelofsizeatmost7konthenumberofverticesBasedonthekernelization，weproposeanimprovedparameterizedalgorithmofrunni

7、ngtime0r24142k)forthe／2一packingproblemFinallythispapersumsupthewholestudyworkonparameterizedalgorithmsto3DmatchingandP2一packingproblemanddiscussesthefurtherworkonsomeotherrelatedproblemsinmatchingandpackingproblemKEYWORD