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

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