本文關(guān)鍵詞：最小賦權(quán)連通k-子圖覆蓋問題的近似算法

  更多相關(guān)文章： 點覆蓋 k-長路覆蓋 連通k-子圖覆蓋 三正則圖

【摘要】：一個頂點子集F被稱作是一個連通k-子圖覆蓋(記作V CCk)如果任意k個點的連通子圖至少有一個頂點在集合F中.最小賦權(quán)的連通k-子圖覆蓋問題(記作MWV CCk)是指找一個權(quán)和最小的頂點子集F使得圖G的頂點集去掉F后剩下的圖不含k個點的連通子圖.這個問題在安全方面和監(jiān)控方面有它的實際背景,它是最小賦權(quán)點覆蓋問題的推廣,而且與最小賦權(quán)k-長路覆蓋問題(記作MWV CPk)有關(guān),這個問題要求每個k-長路中的點至少有一個頂點在子集F中.通過線性規(guī)劃的舍入技巧很容易得到一個k-近似算法.在本文中,首先,我們提出了一個與MWV CPk相關(guān)的模型,即抽象化為一般圖中連通k-子圖覆蓋問題,它是對MWV CPk問題的一種松弛,并且在假定給出圖的圍長(最短圈的長度)至少為k的條件下,我們給出了該問題在賦權(quán)情況下的k-1-近似算法,而且構(gòu)造出了一些例子,來說明對于我們這個算法其k-1是緊的,對于k=3,在[30]中,涂建華等人對于MWV CP3問題給出了一個2-近似算法,由于MWV CP3和MWV CC3是同一個問題,而且一個簡單圖的圍長至少為3,因此,涂等人的結(jié)果[30]被包含在我們的結(jié)果中.其次,在正則圖中,我們也得到了一些比較好的結(jié)果,對于k=3,4,5,分別得到了54,2,3.5-近似算法,并對于k=3,4的情形,構(gòu)造出了相應(yīng)的緊例子,對于一般的k,k≥6,若k是偶數(shù),得到k2-近似,若k是奇數(shù),得到3k4-近似.最后,我們做了簡單的總結(jié),并且討論了今后我們所感興趣的領(lǐng)域.
【關(guān)鍵詞】：點覆蓋 k-長路覆蓋 連通k-子圖覆蓋 三正則圖
【學(xué)位授予單位】：新疆大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要2-3
• 英文摘要3-5
• 第一章 引言5-8
• 1.1 研究背景5-6
• 1.2 研究現(xiàn)狀6-7
• 1.3 本論文的主要結(jié)果7-8
• 第二章 一般圖中連通k-子圖覆蓋問題的近似算法8-14
• 2.1 預(yù)備知識8-10
• 2.2 算法10-11
• 2.3 近似比及復(fù)雜度分析11-14
• 第三章 三正則圖中連通k-子圖覆蓋問題的近似算法14-20
• 3.1 預(yù)備知識14-16
• 3.2 近似算法16-17
• 3.3 近似比分析17-20
• 第四章 討論及總結(jié)20-21
• 參考文獻21-24
• 碩士期間發(fā)表及完成論文清單24-25
• 致謝25-26

【共引文獻】

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前2條

1 崔振華;覆蓋約束條件下的平行機排序問題的算法研究[D];清華大學(xué);2013年

2 李玉超;頂點覆蓋k-路問題的研究和富勒烯圖的參數(shù)計算[D];北京化工大學(xué);2014年

，

本文編號：1031812