Distributed Domination on Graph Classes of Bounded Expansion

Prelegent(ci)

Sebastian Siebertz

Afiliacja

Uniwersytet Warszawski

Termin

29 marca 2017 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

We provide a new constant factor approximation algorithm for the (connected) distance-r dominating set problem on graph classes of bounded expansion. Classes of bounded expansion include many familiar classes of sparse graphs such as planar graphs and graphs with excluded (topological) minors, and notably, these classes form the most general subgraph closed classes of graphs for which a sequential constant factor approximation algorithm for the distance-r dominating set problem is currently known. Our algorithm can be implemented in the CONGEST-BroadCast model of distributed computing and uses O(r^2*log n) communication rounds.

---