检索结果-内蒙古大学图书馆

22nd Annual European Symposium on algorithms (ESA) held as part of ALGO Meeting

作者： Even, Guy Medina, Moti Ron, Dana Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

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 centralized local 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.

关键词： centralized local algorithms Sublinear Approximation algorithms Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Best of two local models: centralized local and distributed local algorithms

引用

INFORMATION AND COMPUTATION 2018年第Part1期262卷 69-89页

作者： Even, Guy Medina, Moti Ron, Dana Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel Ben Gurion Univ Negev Dept Elect & Comp Engn IL-8410501 Beer Sheva Israel

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 centralized local 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.

关键词： centralized local algorithms Sublinear approximation algorithms Graph algorithms Distributed local algorithms Maximum matching Maximum weighted matching

来源：评论

学校读者我要写书评

暂无评论

Distributed Maximum Matching in Bounded Degree Graphs 15

Distributed Maximum Matching in Bounded Degree Graphs

引用

16th International Conference on Distributed Computing and Networking

作者： Even, Guy Medina, Moti Ron, Dana Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

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.

关键词： centralized local algorithms Distributed local algorithms Maximum Matching Maximum Weighted Matching Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：