ﻻ يوجد ملخص باللغة العربية
Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can be much more efficient compared with computing exact solutions. In this paper, we give a near complete characterization of the trade-offs between approximation ratios and round complexity of distributed algorithms for approximating these parameters, with a focus on the weighted and directed variants. Furthermore, we study emph{bi-chromatic} variants of these parameters defined on a graph whose vertices are colored either red or blue, and one focuses only on distances for pairs of vertices that are colored differently. Motivated by applications in computational geometry, bi-chromatic diameter, radius and eccentricities have been recently studied in the sequential setting [Backurs et al. STOC18, Dalirrooyfard et al. ICALP19]. We provide the first distributed upper and lower bounds for such problems. Our technical contributions include introducing the notion of emph{approximate pseudo-center}, which extends the emph{pseudo-centers} of [Choudhary and Gold SODA20], and presenting an efficient distributed algorithm for computing approximate pseudo-centers. On the lower bound side, our constructions introduce the usage of new functions into the framework of reductions from 2-party communication complexity to distributed algorithms.
We give a new, simple distributed algorithm for graph colouring in paths and cycles. Our algorithm is fast and self-contained, it does not need any globally consistent orientation, and it reduces the number of colours from $10^{100}$ to $3$ in three iterations.
In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in scheduling. It was proved by Hasemann, H
This paper introduces a new resource allocation problem in distributed computing called distributed serving with mobile servers (DSMS). In DSMS, there are $k$ identical mobile servers residing at the processors of a network. At arbitrary points of ti
Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a emph{distributed interactive proof} for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed
We study the maximum cardinality matching problem in a standard distributed setting, where the nodes $V$ of a given $n$-node network graph $G=(V,E)$ communicate over the edges $E$ in synchronous rounds. More specifically, we consider the distributed