反饋集與子集反饋集問題的計算復(fù)雜性研究進展

摘要： 反饋集問題（feedback set problem）是計算機科學(xué)中研究最為廣泛和深入的圖上NP完全問題之一，其在并發(fā)計算、大規(guī)模集成電路、編碼設(shè)計、軟件驗證、社交網(wǎng)絡(luò)分析等領(lǐng)域均存在重要的應(yīng)用.子集反饋集問題（subset feedback set problem）是反饋集問題的一種更一般化的形式，更加具有普適性和實用性.近年來，這2個問題在計算復(fù)雜性上的分類工作已逐步完善，... （共15頁）