Vi tillhandahåller en ny konstant faktor approximation algoritm för (anslutna) distans-r dominerande set problem på graf klasser av avgränsad expansion. Klasser av begränsad expansion inkluderar många bekanta klasser av glesa grafer såsom plana grafer och grafer med uteslutna (topologiska) minderåriga, och i synnerhet, dessa klasser utgör de mest allmänna subgraf slutna klasser av grafer för vilka en sekventiell konstant faktor approximation algoritm för avstånd-r dominerande set problem är för närvarande känd. Vår algoritm kan implementeras i CONGEST BC-modellen av distribuerade datorer och använder O(r 2 log n) kommunikationsrundor. Våra tekniker, som kan vara av oberoende intresse, är baserade på en distribuerad beräkning av glesa kvarter täcker av liten radie på avgränsade expansion klasser. Vi visar hur man beräknar en r-neighborhood cover av radien 2r och överlappning f (r ) på varje klass av avgränsad expansion i O(r 2 log n) kommunikationsrundor för någon funktion f. Slutligen visar vi hur man använder den större kraften i LOCAL modellen för att vända någon distans-r dominerande set till en ständigt större ansluten distans-r dominerande set i 3r + 1 rundar på någon klass av avgränsad expansion. Kombinera denna algoritm, t.ex., med konstant faktor approximation algoritm för att dominera uppsättningar på plana grafer av Lenzen et al. ger en konstant faktor approximation algoritm för anslutna dominerande uppsättningar på plana grafer Tillstånd att göra digitala eller hårda kopior av hela eller en del av detta arbete för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior bär detta meddelande och den fullständiga citering på första sidan. Upphovsrätt till delar av detta verk som ägs av andra än upphovsmannen måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, eller återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Begär tillstånd från authoritys@acm.org. SPAA '18, 16-18 juli 2018, Wien, Österrike © 2018 Copyright som innehas av ägaren/författarna. Utgivningsrättigheter som är licensierade till ACM. Kommissionens genomförandeförordning (EU) nr 668/2014 av den 13 juni 2014 om tillämpningsföreskrifter för Europaparlamentets och rådets förordning (EU) nr 1151/2012 om kvalitetsordningar för jordbruksprodukter och livsmedel (EUT L 179, 19.6.2014, s. 1). ... $ 15.00 https://doi.org/10. 1145/3210377.3210383 i ett konstant antal rundor i LOCAL-modellen, där approximationen endast är 6 gånger större än Lenzen et al. Det är algoritmen.
Det är den enda kända algoritmen som löser problemet på en icke-trivial klass av grafer (t.ex. banor, cliques är bland triviala klasser av grafer) är algoritmen för Amiri et al. REF för avgränsade expansionsdiagram som ger en konstant faktor approximation i ett logaritmiskt antal rundor.
Distributed Domination on Graph Classes of Bounded Expansion
{'venue': "SPAA '18", 'journal': None, 'mag_field_of_study': ['Computer Science']}