En oriktad graf består av en uppsättning hörn och en uppsättning oriktade kanter mellan hörn. En sådan graf kan innehålla ett överflöd av cykler, då en feedback vertex uppsättning (FVS) är en uppsättning hörn skär med var och en av dessa cykler. Att konstruera en FVS-kardinalitet som närmar sig det globala minimivärdet är ett optimeringsproblem i den icke-deterministiska polynom-kompletta komplexitetsklassen, därför kan det vara extremt svårt för några stora grafexampel. I den här artikeln utvecklar vi en simulerad glödlampande lokal sökalgoritm för det oriktade FVS-problemet. Genom att definiera en ordning för hörnen utanför FVS, ersätter vi den globala cykeln begränsningar med en uppsättning lokala vertex begränsningar på denna ordning. Under dessa lokala begränsningar minskas kardinaliteten för den fokala FVS gradvis genom den simulerade glödande dynamiska processen. Vi testar denna heuristiska algoritm på stora fall av Erödos-Renyi slumpmässig graf och regelbunden slumpmässig graf, och finner att denna algoritm är jämförbar i prestanda med den trosstyrda decimeringsalgoritmen.
Under 2014 föreslog Qin och Zhou REF det Simulated Annealing Local Searching Protocol for the Undirected FVSP (SALS) baserat på arbetet av Galinier et al. Denna algoritm är endast tillämplig på den oriktade grafversionen av FVSP.
Solving the undirected feedback vertex set problem by local search
{'venue': None, 'journal': 'The European Physical Journal B', 'mag_field_of_study': ['Physics', 'Computer Science']}