Node and edge averaged complexities of local graph problems
Abstract We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph $$G=(V,E)$$...
Main Authors: | Balliu, Alkida, Ghaffari, Mohsen, Kuhn, Fabian, Olivetti, Dennis |
---|---|
Other Authors: | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
Format: | Article |
Language: | English |
Published: |
Springer Berlin Heidelberg
2023
|
Online Access: | https://hdl.handle.net/1721.1/151070 |
Similar Items
-
Improved distributed algorithms for fundamental graph problems
by: Ghaffari, Mohsen
Published: (2017) -
Local Algorithms for Sparsification of Average-case Graphs
by: Cao, Ruidi
Published: (2022) -
Co-embedding of edges and nodes with deep graph convolutional neural networks
by: Yuchen Zhou, et al.
Published: (2023-10-01) -
Random planar graphs with n nodes and a fixed number of edges.
by: Gerke, S, et al.
Published: (2005) -
Average properties of combinatorial problems and thermodynamics of spin models on graphs
by: Alessandro Vezzani, et al.
Published: (2003-01-01)