För en given graf med viktade hörn, målet med den minsta vikt dominerande set problem är att beräkna en vertex delmängd av minsta vikt sådan att varje vertex av grafen ingår i delmängd eller har en granne i delmängd. En enhet diskkurva är en graf där varje vertex motsvarar en enhet disk i planet och två hörn är intilliggande om och endast om deras diskar har en icke-tom skärningspunkt. Vi presenterar den första approximationsalgoritmen med konstant faktor för minimivikts dominerande set-problem i enhetsdiskgrafer, ett problem som motiveras av tillämpningar i trådlösa ad-hoc-nätverk. Algoritmen erhålls i två steg: För det första reduceras problemet till problemet med att täcka en uppsättning punkter som ligger i en liten kvadrat med hjälp av en minimivikt uppsättning enhet diskar. Därefter erhålls en approximationsalgoritm med konstant faktor för det senare problemet med hjälp av uppräknings- och dynamiska programmeringstekniker som utnyttjar enhetsdiskarnas geometri. Dessutom visar vi hur man får en approximationsalgoritm med konstant faktor för minimalviktsansluten dominerande set-problem i enhetsdiskgrafer. Våra tekniker ger också en approximationsalgoritm för konstant faktor för det viktade diskomslagsproblemet (som täcker en uppsättning punkter i planet med enhetsdiskar av minsta totalvikt) och en 3-approximationsalgoritm för det viktade spediteringsproblemet (som täcker en uppsättning punkter i planet med viktade enhetsdiskar vars centra alla ingår i en given enhet disk).
Den första konstanta approximationsalgoritmen för det viktade (1, 1)-CDS-problemet i enhetsdiskgrafer berodde på Ambühl et al. Hoppa över det.
Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs
{'venue': 'In: Proc. of the 9 th Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). (2006', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}