Node and edge averaged complexities of local graph problems
From MaRDI portal
Publication:6071120
DOI10.1007/s00446-023-00453-1arXiv2208.08213OpenAlexW4383218071MaRDI QIDQ6071120
Dennis Olivetti, Mohsen Ghaffari, Alkida Balliu, Fabian Kuhn
Publication date: 21 November 2023
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2208.08213
Cites Work
- Unnamed Item
- Symmetry breaking depending on the chromatic number or the neighborhood growth
- A fast and simple randomized parallel algorithm for maximal matching
- Removing randomness in parallel computation without a processor penalty
- Simple distributed \(\Delta+1\)-coloring of graphs
- Improved deterministic distributed matching via rounding
- Local Computation
- The Locality of Distributed Symmetry Breaking
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- Distributed Computing: A Locality-Sensitive Approach
- Random lifts of graphs: Independence and chromatic number
- An Improved Distributed Algorithm for Maximal Independent Set
- Distributed Degree Splitting, Edge Coloring, and Orientations
- Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses
- Exponential Separations in the Energy Complexity of Leader Election
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Distributed Approximate Maximum Matching in the CONGEST Model.
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- Efficient algorithms for leader election in radio networks
- An optimal distributed (Δ+1)-coloring algorithm?
- Distributed (∆+1)-coloring in sublogarithmic rounds
- A lower bound for the distributed Lovász local lemma
- Brief Announcement
- Distributed Approximation of Maximum Independent Set and Maximum Matching
- Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
- What cannot be computed locally!
- Sleeping is Efficient: MIS in O (1)-rounds Node-averaged Awake Complexity
- The Energy Complexity of BFS in Radio Networks
- How long it takes for an ordinary node with an ordinary ID to output?
This page was built for publication: Node and edge averaged complexities of local graph problems
