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

Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs

THEORETICAL COMPUTER SCIENCE 2017年 662卷 1-8页

作者： Czygrinow, A. Hanckowiak, M. Szymanska, E. Wawrzyniak, W. Witkowski, M. Arizona State Univ Sch Math & Stat Sci Tempe AZ 85287 USA Adam Mickiewicz Univ Fac Math & Comp Sci Poznan Poland

In this paper we consider the 2-dominating set problem (2MDS). We look for a smallest subset of vertices D subset of V with the property that every vertex in V \ D is adjacent to at least 2 vertices of D. We are interested in the distributed complexity of this problem in the local model, where the nodes have no identifiers but there is a port ordering available. We propose a distributed local (constant time) algorithm yielding a 6-approximation in the class of planar graphs. Earlier result shows that in this case, for any is an element of > 0, there is no deterministic distributed local/constant-round algorithm providing.a (5-is an element of)-approximation of the 2MDS. (C) 2016 Elsevier B.V. All rights reserved.

关键词： distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

MIDAS: Multilinear detection at scale

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2019年 132卷 363-382页

作者： Ekanayake, Saliya Cadena, Jose Wickramasinghe, Udayanga Vullikanti, Anil Lawrence Berkeley Natl Lab Performance & Algorithms Res PAR Grp Berkeley CA USA Lawrence Livermore Natl Lab Computat Engn Div Livermore CA 94550 USA Indiana Univ Dept Comp Sci Bloomington IN 47405 USA Univ Virginia Dept Comp Sci Charlottesville VA 22903 USA Univ Virginia Biocomplex Inst & Initiat Charlottesville VA 22903 USA

We focus on two classes of problems in graph mining: (1) finding trees and (2) anomaly detection in complex networks using scan statistics. These are fundamental problems in a broad class of applications. Most of the parallel algorithms for such problems are either based on heuristics, which do not scale very well, or use techniques like color coding, which have a high memory overhead. In this paper, we develop a novel approach for parallelizing both these classes of problems, using an algebraic representation of subgraphs as monomials-this methodology involves detecting multilinear terms in multivariate polynomials. Our algorithms show good scaling over a large regime, and they run on networks with close to half one billion edges. The resulting parallel algorithm for trees is able to scale to subgraphs of size 18, which has not been done before, and it significantly outperforms the best prior color coding based method (FASCIA) by more than two orders of magnitude. Our algorithm for network scan statistics is the first such parallelization, and it is able to handle a broad class of scan statistics functions with the same approach. Published by Elsevier Inc.

关键词： Subgraph isomorphism distributed graph algorithms graph scan statistics Multilinear detection Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The sparsest additive spanner via multiple weighted BFS trees

引用

THEORETICAL COMPUTER SCIENCE 2020年 840卷 33-44页

作者： Censor-Hillel, Keren Paz, Ami Ravid, Noam Technion Dept Comp Sci Haifa Israel Univ Vienna Fac Comp Sci Vienna Austria

Spanners are fundamental graph structures that sparsify graphs at the cost of small stretch. In particular, in recent years, many sequential algorithms constructing additive all-pairs spanners were designed, providing very sparse small-stretch subgraphs. Remarkably, it was then shown that the known (+6)-spanner constructions are essentially the sparsest possible, that is, larger additive stretch cannot guarantee a sparser spanner, which brought the stretch-sparsity trade-off to its limit. distributed constructions of spanners are also abundant. However, for additive spanners, while there were algorithms constructing (+2) and (+4)-all-pairs spanners, the sparsest case of (+6)-spanners remained elusive. We remedy this by designing a new sequential algorithm for constructing a (+6)-spanner with the essentially-optimal sparsity of (O) over tilde (n(4/3)) edges. We then show a distributed implementation of our algorithm, answering an open problem in [12]. A main ingredient in our distributed algorithm is an efficient construction of multiple weighted BFS trees. A weighted BFS tree is a BFS tree in a weighted graph, that consists of the lightest among all shortest paths from the root to each node. We present a distributed algorithm in the CONGEST model, that constructs multiple weighted BFS trees in vertical bar S vertical bar + D - 1 rounds, where S is the set of sources and D is the diameter of the network graph. (C) 2020 Elsevier B.V. All rights reserved.

关键词： distributed graph algorithms Congest model Weighted BFS trees Additive spanners

来源：评论

学校读者我要写书评

暂无评论

An experimental analysis of simple, distributed vertex coloring algorithms

引用

ALGORITHMICA 2005年第1期41卷 1-23页

作者： Finocchi, I Panconesi, A Silvestri, R Univ Roma Tor Vergata Dept Comp Sci Syst & Prod I-00133 Rome Italy Univ Roma La Sapienza Dept Comp Sci I-00198 Rome Italy

We perform an extensive experimental evaluation of very simple, distributed, randomized algorithms for(Delta+1) and so-called Brooks-Vizing vertex colorings, i.e., colorings using considerably fewer than Delta Colors (here Delta denotes the maximum degree of the graph). We consider variants of algorithms known from the literature, boosting them with a distributed independent set computation. Our study clearly determines the relative performance of the algorithms with respect to the number of communication rounds and the number of colors. The results are confirmed by all the experiments and instance families. The empirical evidence shows that some algorithms use very few rounds and are rather effective, thus being amenable to be used in practice.

关键词： distributed graph algorithms vertex coloring algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Local certification of graphs with bounded genus

引用

DISCRETE APPLIED MATHEMATICS 2023年 325卷 9-36页

作者： Feuilloley, Laurent Fraigniaud, Pierre Montealegre, Pedro Rapaport, Ivan Remila, Eric Todinca, Ioan Univ Lyon 1 Univ Lyon LIRIS UMR CNRS 5205 F-69621 Lyon France CNRS IRIF Paris France Univ Paris Cite Paris France Univ Adolfo Ibanez Fac Ingn & Ciencias Santiago Chile Univ Chile DIM CMM UMI CNRS 2807 Santiago Chile Univ Lyon UJM St Etienne GATE L SE UMR 5824 St Etienne France Univ Orleans LIFO Orleans France INSA Ctr Val Loire Orleans France

Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a dMAM(O(log n)) protocol for this class, that is, a distributed interactive protocol with O(log n)-bit proof size in n-node graphs, and three interactions between the (centralized) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corol-lary, there is a dMAM(O(log n)) protocol for recognizing the class of planar graphs, as well as for recognizing the class of graphs with bounded *** show that there exists a distributed interactive protocol for recognizing the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of O(log n) bits. This result also holds for the class of graphs with bounded non-orientable genus, that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schemes do not require any randomization from the verifier, and the proofs may often be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded non-orientable genus. (c) 2022 Elsevier B.V. All rights reserved.

关键词： distributed graph algorithms Local certification Proof-labeling scheme Locally checkable proofs

来源：评论

学校读者我要写书评

暂无评论

The power of locality: Exploring the limits of randomness in distributed computing

引用

IT-INFORMATION TECHNOLOGY 2020年第5-6期62卷 271-278页

作者： Maus, Yannic Israel Inst Technol Technion Haifa Israel

Many modern systems are built on top of large-scale networks like the Internet. This article provides an overview of a dissertation [29] that addresses the complexity of classic graph problems like the vertex coloring problem in such networks. It has been known for a long time that randomization helps significantly in solving many of these problems, whereas the best known deterministic algorithms have been exponentially slower. In the first part of the dissertation we use a complexity theoretic approach to show that several problems are complete in the following sense: An efficient deterministic algorithm for any complete problem would imply an efficient algorithm for all problems that can be solved efficiently with a randomized algorithm. Among the complete problems is a rudimentary looking graph coloring problem that can be solved by a randomized algorithm without any communication. In further parts of the dissertation we develop efficient distributed algorithms for several problems where the most important problems are distributed versions of integer linear programs, the vertex coloring problem and the edge coloring problem. We also prove a lower bound on the runtime of any deterministic algorithm that solves the vertex coloring problem in a weak variant of the standard model of the area.

关键词： distributed graph algorithms Randomization Deterministic Reductions Completeness LOCAL model Vertex coloring Edge coloring

来源：评论

学校读者我要写书评

暂无评论

Fast distributed algorithms for Connectivity and MST in Large graphs

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2018年第1期5卷 4.1-4.22页

作者： Pandurangan, Gopal Robinson, Peter Scquizzato, Michele Univ Houston Dept Comp Sci Houston TX 77004 USA Royal Holloway Univ London London England McMaster Univ Dept Comp & Software Hamilton ON L8S 4K1 Canada KTH Royal Inst Technol Sch Elect Engn & Comp Sci SE-10044 Stockholm Sweden

Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of fundamental graph problems in a message-passing model for distributed computing where k >= 2 machines jointly perform computations on graphs with n nodes (typically, n >> k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main result is an (almost) optimal distributed randomized algorithm for graph connectivity. Our algorithm runs in (O) over tilde (n/k(2)) rounds ((O) over tilde notation hides a polylog(n) factor and an additive polylog(n) term). This improves over the best previously known bound of (O) over tilde (n/k) [Klauck et al., SODA 2015] and is optimal (up to a polylogarithmic factor) in light of an existing lower bound of (Omega) over tilde (n/k(2)). Our improved algorithm uses a bunch of techniques, including linear graph sketching, that prove useful in the design of efficient distributed graph algorithms. Using the connectivity algorithm as a building block, we then present fast randomized algorithms for computing minimum spanning trees, (approximate) min-cuts, and for many graph verification problems. All these algorithms take (O) over tilde (n/k(2)) rounds and are optimal up to polylogarithmic factors. We also show an almost matching lower bound of (Omega) over tilde (n/k(2)) rounds for many graph verification problems by leveraging lower bounds in random-partition communication complexity.

关键词： distributed graph algorithms graph sketching graph connectivity minimum spanning trees

来源：评论

学校读者我要写书评

暂无评论

Near-optimal distributed Triangle Enumeration via Expander Decompositions

引用

JOURNAL OF THE ACM 2021年第3期68卷 1–36页

作者： Chang, Yi-Jun Pettie, Seth Saranurak, Thatchaphol Zhang, Hengjie Swiss Fed Inst Technol Inst Theoret Studies Clausiusstr 47 CH-8092 Zurich Switzerland Univ Michigan Comp Sci & Engn 2260 Hayward St Ann Arbor MI 48109 USA Columbia Univ Dept Comp Sci 500 W 120th St New York NY 10027 USA

We present improved distributed algorithms for variants of the triangle finding problem in the CONGEST modeL We show that triangle detection, counting, and enumeration can be solved in (O) over tilden(1/3)) rounds using expander decompositions. This matches the triangle enumeration lower bound of (Omega) over tilde (n(1/3)) by Izumi and Le Gall [PODC'17] and Pandurangan, Robinson, and Scquizzato [SPAA'18], which holds even in the CONGESTED-CLIQUE model. The previous upper bounds for triangle detection and enumeration in CONGEST were (O) over tilde (n(2/3)) and (O) over tilde (n(3/4)), respectively, due to Izumi and Le Gall [PODC'17]. An (epsilon, phi)-expander decomposition of a graph G = (V, E) is a clustering of the vertices V = V-1 boolean OR ... boolean OR V-x such that (i) each cluster V;induces a subgraph with conductance at least phi and (ii) the number of inter-cluster edges is at most epsilon vertical bar E vertical bar. We show that an (epsilon, phi)-expander decomposition with phi = (epsilon/ log n)(2o(k)) can be constructed in O(n(2/k) . poly(1/phi, log n)) rounds for any epsilon is an element of (0, 1) and positive integer k. For example, a (1/n(o(1)), 1/n(o(1)))-expander decomposition only requires n(o(1)) rounds to compute, which is optimal up to subpolynomial factors, and a (0.1. 1/poly log n)-expander decomposition can be computed in O (n(gamma)) rounds, for any arbitrarily small constant gamma > 0. Our triangle finding algorithms are based on the following generic framework using expander decompositions, which is of independent interest. We first construct an expander decomposition. For each cluster, we simulate CONGESTED-CLIQUE algorithms with small overhead by applying the expander routing algorithm due to Ghaffari, Kuhn, and Su [PODC'17] Finally, we deal with inter-cluster edges using recursive calls.

关键词： CONGEST distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Minor Sparsifiers and the distributed Laplacian Paradigm 62

Minor Sparsifiers and the Distributed Laplacian Paradigm

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Forster, Sebastian Goranci, Gramoz Liu, Yang P. Peng, Richard Sun, Xiaorui Ye, Mingquan Univ Salzburg Dept Comp Sci Salzburg Austria Univ Glasgow Sch Comp Sci Glasgow Lanark Scotland Stanford Univ Dept Math Palo Alto CA 94304 USA Georgia Tech Sch Comp Sci Atlanta GA USA Univ Waterloo Waterloo ON Canada Univ Illinois Dept Comp Sci Chicago IL USA

ISBN: (纸本)9781665420556

We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrices to high accuracy. Our Laplacian solver has a round complexity of O(n(o(1))(root n + D)), and thus almost matches the lower bound of (Omega) over tilde(root n+D), where n is the number of nodes in the network and D is its diameter. We show that our distributed solver yields new sublinear round algorithms for several cornerstone problems in combinatorial optimization. This is achieved by leveraging the powerful algorithmic framework of Interior Point Methods (IPMs) and the Laplacian paradigm in the context of distributed graph algorithms, which entails numerically solving optimization problems on graphs via a series of Laplacian systems. Problems that benefit from our distributed algorithmic paradigm include exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on sparse directed graphs. For the maxflow problem, this is the first exact distributed algorithm that applies to directed graphs, while the previous work by [Ghaffari et al. SICOMP'18] considered the approximate setting and works only for undirected graphs. For the mincost flow and the negative weight shortest path problems, our results constitute the first exact distributed algorithms running in a sublinear number of rounds. Given that the hybrid between IPMs and the Laplacian paradigm has proven useful for tackling numerous optimization problems in the centralized setting, we believe that our distributed solver will find future applications. At the heart of our distributed Laplacian solver is the notion of spectral subspace sparsifiers of [Li, Schild FOCS'18]. We present a nontrivial distributed implementation of their construction by (i) giving a parallel variant of their algorithm that avoids the sampling of random spanning trees and uses approximate leverage scores instead, and (ii) showing that t

关键词： distributed graph algorithms Laplacian solvers minor-based sparsification

来源：评论

学校读者我要写书评

暂无评论

Local distributed algorithms in Highly Dynamic Networks 33

Local Distributed Algorithms in Highly Dynamic Networks

引用

33rd IEEE International Parallel and distributed Processing Symposium (IPDPS)

作者： Bamberger, Philipp Kuhn, Fabian Maus, Yannic Univ Freiburg Freiburg Germany

ISBN: (纸本)9781728112466

We define a generalization of local distributed graph problems to (synchronous round-based) dynamic networks and present a framework for developing algorithms for these problems. The algorithms should satisfy non-trivial guarantees in every round. The guarantees should be stronger the more stable the graph has been during the last few rounds and coincide with the definition of the static graph problem if no topological change appeared recently. Moreover, if only a constant neighborhood around some part of the graph is stable during an interval, the algorithms should quickly converge to a solution for this part of the graph that remains unchanged throughout the interval. We demonstrate our generic framework with two classic distributed graph problems, namely (degree+1)-vertex coloring and maximal independent set (MIS). To illustrate the given guarantees consider the vertex coloring problem: Any conflict between two nodes caused by a newly inserted edge is resolved within T = O(log n) rounds. During this conflict resolving both nodes always output colors that are not in conflict with their respective 'old' neighbors. The largest color that a node is allowed to output is determined by the number of distinct neighbors that it has seen in the last T rounds.

关键词： highly dynamic networks distributed graph algorithms maximal independent set (MIS) vertex coloring

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：