I trådlösa sensornätverk har en virtuell ryggrad föreslagits som routing infrastruktur för att lindra problemet med radio- och tv-sändningar storm och utföra vissa andra uppgifter som områdesövervakning. Tidigare arbete inom detta område har främst fokuserat på hur man kan skapa en liten virtuell ryggrad för hög effektivitet, som är modellerad som minsta Connected Dominating Set (CDS) problem. I detta dokument överväger vi hur vi ska skapa en liten virtuell ryggrad för att balansera effektivitet och feltolerans. Detta problem kan formaliseras som minsta m-anslutna k-tuple dominerande set problem, vilket är en allmän version av minsta CDS problem med m = 1 och k = 1. Vi föreslår tre centraliserade algoritmer med små approximationsförhållanden för små m och förbättrar dagens bästa resultat för små k.
Författarna i REF fokuserar på minsta m-anslutna k-tuple dominerande set-problem.
Algorithms for minimum m-connected k-tuple dominating set problem
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}