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

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