I trådlösa ad hoc-nätverk kan ett uppkopplat dominerande set användas som en virtuell ryggrad för att förbättra prestandan. Många konstruktioner för att approximera den minsta anslutna dominerande setet bygger på byggandet av en maximal oberoende set. Förhållandet mellan storleken mis(G) för en maximal oberoende uppsättning och storleken cds(G) för en minsta ansluten dominerande uppsättning i samma diagram G spelar en viktig roll för att fastställa prestandaförhållandet för dessa approximationsalgoritmer. Tidigare är det känt att mis(G) 4 · cds(G) + 1 för alla enhet disk grafer G. I detta papper, vi förbättra det genom att visa mis(G) 3.8 · cds(G) + 1.2.
Wu och Al. REF införde en distribuerad CDS-konstruktionsalgoritm som bygger på förhållandet mellan den maximala oberoende uppsättningen (MIS) och den anslutna dominerande uppsättningen.
Minimum connected dominating sets and maximal independent sets in unit disk graphs
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}