Node labels in local decision
From MaRDI portal
Publication:1625609
DOI10.1016/j.tcs.2017.01.011zbMath1409.68045arXiv1507.00909OpenAlexW2953154319MaRDI QIDQ1625609
Pierre Fraigniaud, Juho Hirvonen, Jukka Suomela
Publication date: 29 November 2018
Published in: Theoretical Computer Science, Structural Information and Communication Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1507.00909
Related Items
Node labels in local decision ⋮ Proof-labeling schemes: broadcast, unicast and in between ⋮ Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ A hierarchy of local decision ⋮ Deciding and verifying network properties locally with few output bits ⋮ Randomized proof-labeling schemes ⋮ Approximate proof-labeling schemes ⋮ Introduction to local certification
Cites Work
- Unnamed Item
- Unnamed Item
- Anonymous wireless rings
- Deterministic local algorithms, unique identifiers, and fractional graph colouring
- Node labels in local decision
- Survey of local algorithms
- Lower bounds for local approximation
- Anonymous networks
- Groupings and Pairings in Anonymous Networks
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- What Can be Computed Locally?
- Assigning labels in an unknown anonymous network with a leader
- Compact and localized distributed data structures
- Hundreds of impossibility results for distributed computing
- Computability in Anonymous Networks: Revocable vs. Irrecovable Outputs
- What can be decided locally without identifiers?
- Distributed Computing with Advice: Information Sensitivity of Graph Coloring
- Local Distributed Decision
- On the Impact of Identifiers on Local Decision
- Weak models of distributed computing, with connections to modal logic
