Problemet med minimivikt Dominating Set (MWDS) är en viktig generalisering av minimi- Dominating Set (MDS) problem med omfattande applikationer. I detta dokument föreslås en ny lokal sökalgoritm för MWDS-problemet, som bygger på två nya idéer. Den första idén är en heurist kallas två-nivå konfiguration kontroll (CC 2 ), som är en ny variant av en nyligen kraftfull konfiguration kontroll strategi (CC) för att effektivt undvika de senaste sökvägarna. Den andra idén är en ny poängfunktion baserad på frekvensen av att avslöjas av hörn. Vår algoritm kallas CC 2 FS, enligt namnen på de två idéerna. De experimentella resultaten visar att CC 2 FS presterar mycket bättre än vissa toppmoderna algoritmer när det gäller lösningskvalitet på ett brett spektrum av MWDS-riktmärken.
Enligt litteraturen kallas den nuvarande bästa heuristiska algoritmen för MWDS-problemet CC 2 FS, som bygger på två nivåers konfigurationskontroll och frekvensbaserad poängfunktion, och har bättre prestanda på ett brett spektrum av riktmärken än andra MWDS-algoritmer REF.
Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
{'venue': 'JAIR 58 (2017) 267-295', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}