Distributed distance domination in graphs with no \(K_{2,t}\)-minor

DOI10.1016/j.tcs.2022.03.001OpenAlexW4220678582MaRDI QIDQ2143127

Andrzej Czygrinow, Marcin Witkowski, Michał Hanćkowiak

Publication date: 31 May 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2203.03229

zbMATH Keywords

distributed algorithmslocal modelsparse graphsdistance dominating set

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed minimum dominating set approximations in restricted families of graphs
• The edge-density for \(K_{2,t}\) minors
• Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• Local Computation
• Fast Distributed Approximations in Planar Graphs
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
• How to Allocate Network Centers
• Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs
• A Local Constant Factor MDS Approximation for Bounded Genus Graphs
• Distributed distance-\(r\) covering problems on sparse high-girth graphs