Distributed CONGESTBC constant approximation of MDS in bounded genus graphs

Andrzej Czygrinow, Michał Hanćkowiak, Wojciech Wawrzyniak, Marcin Witkowski

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


We give a distributed algorithm which finds a constant approximation of a minimum dominating set in graphs of constant genus. The algorithm works in the CONGESTBC model (distributed, synchronous, with short messages and broadcast type of transmissions) and runs in a constant number of distributed rounds.

Original languageEnglish (US)
Pages (from-to)1-10
Number of pages10
JournalTheoretical Computer Science
StatePublished - Jan 24 2019


  • Bounded genus graphs
  • Distributed algorithms
  • Local algorithms
  • Minimum dominating set

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Distributed CONGESTBC constant approximation of MDS in bounded genus graphs'. Together they form a unique fingerprint.

Cite this