A time-optimal randomized parallel algorithm for mis

[PDF] arxiv.org

Local computation of maximal independent set

M Ghaffari - 2022 IEEE 63rd Annual Symposium on …, 2022 - ieeexplore.ieee.org
We present a randomized Local Computation Algorithm (LCA) with query complexity poly
(Δ)⋅\logn for the Maximal Independent Set (MIS) problem. That is, the algorithm determines …
被引用次数：16 相关文章 所有 5 个版本
[PDF] arxiv.org

Invitation to Local Algorithms

V Rozhoň - arXiv preprint arXiv:2406.19430, 2024 - arxiv.org
This text provides an introduction to the field of distributed local algorithms--an area at the
intersection of theoretical computer science and discrete mathematics. We collect many …
相关文章

Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph

W Hong, Y Ran, Z Zhang - Theoretical Computer Science, 2022 - Elsevier
In a minimum general partial dominating set problem (MinGPDS), given a graph G=(V, E), a
profit function p: V→ R+ and a threshold K, the goal is to find a minimum subset of vertices …
被引用次数：1 相关文章 所有 2 个版本
[PDF] arxiv.org

A parallel algorithm for minimum weight set cover with small neighborhood property

Y Ran, Y Zhang, Z Zhang - arXiv preprint arXiv:2202.03872, 2022 - arxiv.org
This paper studies the minimum weight set cover (MinWSC) problem with a {\em small
neighborhood cover}(SNC) property proposed by Agarwal {\it et al.} in\cite {Agarwal.}. A …
相关文章 所有 2 个版本

Parallel Algorithm for Minimum Partial Dominating Set in Unit Disk Graph

W Hong, Z Zhang, Y Ran - International Conference on Combinatorial …, 2021 - Springer
In this paper, we consider the minimum partial dominating set problem in unit disk graphs
(MinPDS-UD). Given a set of points V on the plane with| V|= n| V|= n, two points in V are …
相关文章 所有 2 个版本