ﻻ يوجد ملخص باللغة العربية
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 CONGEST model, where in each round, each node of $G$ can send an $O(log n)$-bit message to each of its neighbors. We show that for every graph $G$ and a matching $M$ of $G$, there is a randomized CONGEST algorithm to verify $M$ being a maximum matching of $G$ in time $O(|M|)$ and disprove it in time $O(D + ell)$, where $D$ is the diameter of $G$ and $ell$ is the length of a shortest augmenting path. We hope that our algorithm constitutes a significant step towards developing a CONGEST algorithm to compute a maximum matching in time $tilde{O}(s^*)$, where $s^*$ is the size of a maximum matching.
We present simple deterministic algorithms for subgraph finding and enumeration in the broadcast CONGEST model of distributed computation: -- For any constant $k$, detecting $k$-paths and trees on $k$ nodes can be done in $O(1)$ rounds. -- For an
We give efficient randomized and deterministic distributed algorithms for computing a distance-$2$ vertex coloring of a graph $G$ in the CONGEST model. In particular, if $Delta$ is the maximum degree of $G$, we show that there is a randomized CONGEST
We present improved results for approximating maximum-weight independent set ($MaxIS$) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let $n$ and $Delta$ be the number of nodes and maximum degree, respectively, and le
Maximum weight matching is one of the most fundamental combinatorial optimization problems with a wide range of applications in data mining and bioinformatics. Developing distributed weighted matching algorithms is challenging due to the sequential n
Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomized distributed vertex coloring algorithm for the standard CONGEST mode