Distributed Domination on Graph Classes of Bounded Expansion

Speaker(s)

Sebastian Siebertz

Affiliation

Uniwersytet Warszawski

Date

March 29, 2017, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---