arXiv Open Access 2019

An $\tilde{O}(\log^2 n)$-approximation algorithm for $2$-edge-connected dominating set

Amir Belgi Zeev Nutov

Lihat Sumber

Abstrak

In the Connected Dominating Set problem we are given a graph $G=(V,E)$ and seek a minimum size dominating set $S \subseteq V$ such that the subgraph $G[S]$ of $G$ induced by $S$ is connected. In the $2$-Edge-Connected Dominating Set problem $G[S]$ should be $2$-edge-connected. We give the first non-trivial approximation algorithm for this problem, with expected approximation ratio $\tilde{O}(\log^2n)$.

Topik & Kata Kunci

cs.DS

Penulis (2)

Amir Belgi

Zeev Nutov

Format Sitasi

APA MLA BibTeX

Belgi, A., Nutov, Z. (2019). An $\tilde{O}(\log^2 n)$-approximation algorithm for $2$-edge-connected dominating set. https://arxiv.org/abs/1912.09662

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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