We design centralized local algorithms for: maximal independent set, maximal matching, and graph coloring. The improvement is threefold: the algorithms are deterministic, stateless, and the number of probes is O(log* ...
详细信息
ISBN:
(纸本)9783662447772;9783662447765
We design centralized local algorithms for: maximal independent set, maximal matching, and graph coloring. The improvement is threefold: the algorithms are deterministic, stateless, and the number of probes is O(log* n), where n is the number of vertices of the input graph. Our algorithms for maximal independent set and maximal matching improves over previous randomized algorithms by Alon et al. (SODA 2012) and Mansour et al. (ICALP 2012). In these previous algorithms, the number of probes and the space required for storing the state between queries are poly(log n). We also design the first centralizedlocal algorithm for graph coloring. Our graph coloring algorithms are deterministic and stateless. Let Delta denote the maximum degree of a graph over n vertices. Our algorithm for coloring the vertices by Delta + 1 colors requires O(log* n) probes for constant degree graphs. Surprisingly, for the case where the number of colors is O(Delta(2) log.), the number of probes of our algorithm is O(Delta . log* n + Delta(2)), that is, the number of probes is sublinear if Delta = o(root n), i.e., our algorithm applies for graphs with unbounded degrees.
We consider two models of computation: centralized local algorithms and local distributed algorithms. algorithms in one model are adapted to the other model to obtain improved algorithms. Distributed vertex coloring i...
详细信息
We consider two models of computation: centralized local algorithms and local distributed algorithms. algorithms in one model are adapted to the other model to obtain improved algorithms. Distributed vertex coloring is employed to design improved centralized local algorithms for: maximal independent set, maximal matching, and an approximation scheme for maximum (weighted) matching over bounded degree graphs. The improvement is threefold: the algorithms are deterministic, stateless, and the number of probes grows polynomially in log* n, where n is the number of vertices of the input graph. The recursive centralizedlocal improvement technique by Nguyen and Onak (FOCS 2008) is employed to obtain a distributed approximation scheme for maximum (weighted) matching. (C) 2018 Elsevier Inc. All rights reserved.
We present deterministic distributed algorithms for computing approximate maximum cardinality matchings and approximate maximum weight matchings. Our algorithm for the unweighted case computes a matching whose size is...
详细信息
ISBN:
(纸本)9781450329286
We present deterministic distributed algorithms for computing approximate maximum cardinality matchings and approximate maximum weight matchings. Our algorithm for the unweighted case computes a matching whose size is at least (1- epsilon) times the optimal in Delta(O(1/epsilon)) + O (1/epsilon(2))center dot log*(n) rounds where n is the number of vertices in the graph and Delta is the maximum degree. Our algorithm for the edge weighted case computes a matching whose weight is at least (1- epsilon) times the optimal in log(min{1/w(min),n/epsilon})(O(1/epsilon)) (Delta(O(1/epsilon))+log*(n)) rounds for edge-weights in [w(min), 1]. The best previous algorithms for both the unweighted case and the weighted case are by Lotker, Patt-Shamir, and Pettie (SPAA 2008). For the unweighted case they give a randomized (1- epsilon)-approximation algorithm that runs in O((log(n))/epsilon(3)) rounds. For the weighted case they give a randomized (1/2- epsilon)-approximation algorithm that runs in O(log(epsilon(-1)) center dot log(n)) rounds. Hence, our results improve on the previous ones when the parameters Delta, epsilon and w(min), are constants (where we reduce the number of runs from O(log(n)) to O(log*(n))), and more generally when Delta, 1/epsilon and 1/w(min) are sufficiently slowly increasing functions of n. Moreover, our algorithms are deterministic rather than randomized.
暂无评论