1 citations · 1 across the 4 of their papers we have counts for
4 papers
Dynamic Approximate Maximum Matching in the Distributed Vertex Partition Model
Peter Robinson, Xianbin Zhu
We initiate the study of approximate maximum matching in the vertex partition model, for graphs subject to dynamic changes. We assume that the vertices of the graph are partiti…
Dynamic Maximal Matching in Clique Networks
Minming Li, Peter Robinson, Xianbin Zhu
We consider the problem of computing a maximal matching with a distributed algorithm in the presence of batch-dynamic changes to the graph topology. We assume that a graph of n…
The Local Information Cost of Distributed Graph Spanners
Peter Robinson
We introduce the \emph{local information cost} (LIC), which quantifies the amount of information that nodes in a network need to learn when solving a graph problem. We show that th…
Latency, Capacity, and Distributed MST
John Augustine, Seth Gilbert, Fabian Kuhn +2
We study the cost of distributed MST construction in the setting where each edge has a latency and a capacity, along with the weight. Edge latencies capture the delay on the links…