超圖上最大獨立集問題的精確算法

摘要： 最大獨立集問題是計算機科學中最基礎且重要的NP完全問題之一.本文研究了超圖上最大獨立集問題(MISH)和超圖上帶懲罰的最大獨立集問題(PC-MISH)的精確算法.給定一個超圖,MISH問題旨在尋找圖中最大的獨立集,其中,超圖中的獨立集是一些兩兩不包含在同一超邊的頂點構成的點子集.而PC-MISH問題是MISH問題的松弛化變體.在PC-MISH問題中,仍然尋找一個點集X,但是它允... （共18頁）