Paw圖–邊刪除問題的線性頂點核心化算法

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