最大可解線性網(wǎng)絡(luò)編碼的計算復(fù)雜性與構(gòu)造方法.pdf

1、復(fù)旦大學碩士學位論文最大可解線性網(wǎng)絡(luò)編碼的計算復(fù)雜性與構(gòu)造方法姓名：劉冠群申請學位級別：碩士專業(yè)：計算機軟件與理論指導(dǎo)教師：闞海斌20100516AbstractNetworkcodingisanewresearchareawhichisaimedtoimprovetheefficiencyoftransmittingmessagesincommunicationnetworksTraditionalroutingonlyallowst

2、heintermediatenodestostoreandforwardthemessages，whilenetworkcodingenablesnodestoencodethemessagesandthenforwardthemThesinksdodecodingtogetoriginalmessagesaftertheyreceiveenoughencodedmessagesInacommunicationnetwork，eachn

3、odecouldgetmessagesatrateofnomorethanitsmaxflowForsinglesourcemulticastnetworks，allthesinkscouldgetmessagessimultaneouslyattherateoftheminimumvalueoftheirmaxflowfurthermore，linearnetworkcodingissufficientinthiscaseHoweve

4、rlinearnetworkcodingformulticastnetworksdoesnotutilizeallthesinkscapacitiesThisthesisproposesanewtypeofnetworkcodethatiscalledmaximumdecodablelinearnetworkcode，underwhicheverysinkcouldgetmessagesattherateofitsownmaxflowa

5、ndcoulddecodethesemessagesThethesisfocusesontwofacetsofmaximumdecodablelinearnetworkcoding：thecomputingcomplexityandtheconstructingmethodWeprovethatitisNP—hardtodecidewhetherthereexistsamaximumdecodablelinearnetworkcodef

6、oragivennetworkfrominformationflowperspectiveandalgebraicperspective；andthenpresentasimplegreedyconstructingalgorithmandanimprovedheuristicmethodtoconstructmaximumdecodablelinearnetworkcodebasedontheimpoaanceofchannelSKe