Eftersom en graf, en ansluten dominerande uppsättning är en delmängd av hörn sådana att varje vertex är antingen i delmängd eller i anslutning till en vertex i delmängd och subgraph induceras av delmängd är ansluten. En minsta anslutna dominerande uppsättning är en sådan vertex delmängd med minsta kardinalitet. I detta dokument presenterar vi ett nytt steg girig approximation med prestanda ratio ln + 2 där är den maximala graden i inmatningskurvan. Den intressanta aspekten är att den giriga potentiella funktionen hos denna algoritm inte är sumodular medan alla tidigare kända giriga algoritmer i ett steg med liknande prestanda har sumodulära potentiella funktioner.
Ruan m.fl. REF presenterade en ny approximationsalgoritm, som är en girig algoritm i ett steg, med ett prestandaförhållande ln δ + 2, där δ är den maximala graden i inmatningskurvan.
A greedy approximation for minimum connected dominating sets
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}