Distributed distance domination in graphs with no $K_{2,t}$-minor

March 07, 2022 Β· Declared Dead Β· πŸ› Theoretical Computer Science

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Andrzej Czygrinow, Michał Hanćkowiak, Marcin Witkowski arXiv ID 2203.03229 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DC Citations 2 Venue Theoretical Computer Science Last Checked 4 months ago
Abstract
We prove that a simple distributed algorithm finds a constant approximation of an optimal distance-$k$ dominating set in graphs with no $K_{2,t}$-minor. The algorithm runs in a constant number of rounds. We further show how this procedure can be used to give a distributed algorithm which given $Ξ΅>0$ and $k,t\in \mathbb{Z}^+$ finds in a graph $G=(V,E)$ with no $K_{2,t}$-minor a distance-$k$ dominating set of size at most $(1+Ξ΅)$ of the optimum. The algorithm runs in $O(\log^*{|V|})$ rounds in the Local model. In particular, both algorithms work in outerplanar graphs.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted