圖邊單射染色問題的復雜性及算法研究.pdf

1、學位論文獨創(chuàng)性聲明本人鄭重聲明：所提交的學位是本人在導師指導下進行的研究工作以及取得的相關研究成果本論文中除引文外，所有數據和有關材料均是真實的本論文中除引文和致謝的內容外，不包含其他人或其它機構已經發(fā)表或撰寫過的研究成果其他同志對本研究所做的貢獻均己在論文中作了聲明并表示了謝意學位論文作者簽名：至貓西日期：加但f7學位論文使用授權聲明研究生在校攻讀學位期間論文工作的知識產權單位屬南京師范大學學校有權保存本學位論文的電子以及紙質文檔，可

2、以借閱或者上網公布本學位論文的部分或者全部內容，可以采用影印、復印等手段保存、匯編本學位論文學?？梢韵驀矣嘘P機關或者機構送交論文的電子和紙質文檔，允許論文被查閱和借閱(保密論文在解密后遵守此規(guī)定)保密論文注釋：本學位論文屬于保密論文，保密期限為年學位論文作者簽名：至飾谫日期：加限6。f7ContentsContentsAbstract(inChinese)111Abstract(inEnglish)VPreface，1Chapter1

3、Introduction311Basicdefinition312Thebackgroundof蛔ectivecoloringproblemandsomeknownresults9Chapter2NPcompletenessofedgeinjecfivecoloring11Chapter3Theapproximationalgorithmforedgeinjectivecoloringofboundedplanargraphsr，153

4、1Thelayeredapproachforedgeinjectivecoloringofboundedplanargraphsandrelevantconclusions1532Approximationalgorithmforedgeinjecfivecoloringofboundeddegreeplanargraphs1SChapter4Theexactalgorithmofedgeinjectivecoloringandrele