Distributed distance-\(r\) covering problems on sparse high-girth graphs

DOI10.1007/978-3-030-75242-2_3OpenAlexW3159901882MaRDI QIDQ5925671

Saeed Akhoondian Amiri, Ben Wiederhake

Publication date: 22 March 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-75242-2_3

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (2)

Distributed distance domination in graphs with no \(K_{2,t}\)-minor ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs

Cites Work

• Unnamed Item
• Distributed minimum dominating set approximations in restricted families of graphs
• Sparsity. Graphs, structures, and algorithms
• On sparse spanners of weighted graphs
• Graph Theory
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• Local Computation
• Distributed Approximation Algorithms for Planar Graphs
• Fast Distributed Approximations in Planar Graphs
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
• Locality in Distributed Graph Algorithms
• Approximation algorithms for NP-complete problems on planar graphs
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Deterministic Distributed Dominating Set Approximation in the CONGEST Model
• Hardness of Distributed Optimization
• Distributed Maximal Independent Set using Small Messages
• What can be computed locally?
• Fast network decomposition
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
• Distributed Approximation on Power Graphs

This page was built for publication: Distributed distance-\(r\) covering problems on sparse high-girth graphs