Paw圖–邊刪除問(wèn)題的線性頂點(diǎn)核心化算法

摘要： 圖邊刪除問(wèn)題中一類(lèi)重要問(wèn)題是研究是否可以刪除圖中不超過(guò)k條邊之后使得剩余的圖不存在某個(gè)子圖結(jié)構(gòu)H,而子圖H為頂點(diǎn)個(gè)數(shù)不超過(guò)4的連通圖的情況被研究得最為廣泛.本文主要考慮H為Paw圖(三角形其中一個(gè)頂點(diǎn)再鄰接一條邊)的情況,稱(chēng)為Paw圖–邊刪除問(wèn)題,并為該問(wèn)題設(shè)計(jì)了一個(gè)32k個(gè)頂點(diǎn)的問(wèn)題核.這是該問(wèn)題的第1個(gè)線性頂點(diǎn)大小的問(wèn)題核.文中主要的技術(shù)是結(jié)合兩個(gè)新的皇冠分解的變體來(lái)分析圖...