Abstract Connected dominating set (CDS) i enhetsdiskgrafer har ett brett spektrum av applikationer i trådlösa ad hoc-nätverk. Ett antal approximativa algoritmer för att bygga en liten CDS i enhet disk grafer har föreslagits i litteraturen. Majoriteten av dessa algoritmer följer en allmän tvåfasig strategi. Den första fasen konstruerar en dominerande uppsättning, och den andra fasen väljer ytterligare noder för att koppla samman noderna i den dominerande uppsättningen. I prestandaanalyserna av dessa tvåfasade algoritmer spelar förhållandet mellan självständighetsnumret α och det anslutna dominansnumret γ c i en enhet-disk graf en nyckelroll. Det mest kända förhållandet mellan dem är α ≤ 3 2 3 γ c + 1. I detta dokument bevisar vi att α ≤ 3.4306γ c + 4.8185. Detta förhållande leder till snävare övre gränser på approximationsförhållandet mellan två approximationsalgoritmer som föreslås i litteraturen.
REF fick ett snävare förhållande mellan självständighetsnumret och det anslutna dominansnumret, och använde ett ganska komplicerat geometriskt argument för att driva detta ytterligare till 3.4306γ + 4.8185.
Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}