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

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