arXiv Open Access 2014

Local Approximability of Minimum Dominating Set on Planar Graphs

Miikka Hilke Christoph Lenzen Jukka Suomela

Lihat Sumber

Abstrak

We show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a $(7-ε)$-approximation of a minimum dominating set on planar graphs, for any positive constant $ε$. In prior work, the best lower bound on the approximation ratio has been $5-ε$; there is also an upper bound of $52$.

Topik & Kata Kunci

cs.DC cs.DS

Penulis (3)

Miikka Hilke

Christoph Lenzen

Jukka Suomela

Format Sitasi

APA MLA BibTeX

Hilke, M., Lenzen, C., Suomela, J. (2014). Local Approximability of Minimum Dominating Set on Planar Graphs. https://arxiv.org/abs/1402.2549

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2014
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓