Locality in Distributed Graph Algorithms
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Local edge colouring of Yao-like subgraphs of unit disk graphs
- Low diameter graph decompositions
- Graph theoretical issues in computer networks
- Computing roots of graphs is hard
- Deterministic broadcasting time with partial knowledge of the network.
- Distributed broadcast in radio networks of unknown topology.
- Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels.
- Generating irregular partitionable data structures
- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- Randomized OBDD-based graph algorithms
- Design patterns in beeping algorithms: examples, emulation, and analysis
- Impact of locality on location aware unit disk graphs
- What can be verified locally?
- Cellular adaptive Petri net based on learning automata and its application to the vertex coloring problem
- Linear-in- lower bounds in the LOCAL model
- Computing large independent sets in a single round
- Constant-time local computation algorithms
- Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge
- Best of two local models: centralized local and distributed local algorithms
- Deterministic distributed construction of T-dominating sets in time T
- On the least distance eigenvalues of the second power of a graph
- Distributed algorithm for approximating the maximum matching
- On the extremal combinatorics of the Hamming space
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- A distributed approximation algorithm for the bottleneck connected dominating set problem
- Sublinear fully distributed partition with applications
- Almost stable matchings by truncating the Gale-Shapley algorithm
- Improved distributed \(\Delta\)-coloring
- Almost global problems in the LOCAL model
- Fast distributed approximation for TAP and 2-edge-connectivity
- Distributed backup placement
- Local mending
- Linial for lists
- Distributed algorithms for fractional coloring
- Distributed graph problems through an automata-theoretic Lens
- Distributed reconfiguration of maximal independent sets
- What can be sampled locally?
- Improved deterministic distributed matching via rounding
- Derandomizing local distributed algorithms under bandwidth restrictions
- A hierarchy of local decision
- Fooling views: a new lower bound technique for distributed computations under congestion
- Combinatorial algorithms for distributed graph coloring
- No sublogarithmic-time approximation scheme for bipartite vertex cover
- Low-weight superimposed codes and related combinatorial structures: bounds and applications
- Local algorithms for sparse spanning graphs
- Distributed coloring in sparse graphs with fewer colors
- Linear-time algorithms for tree root problems
- Distributed coloring algorithms for triangle-free graphs
- Allowing each node to communicate only once in a distributed system: shared whiteboard models
- Coloring unstructured radio networks
- Distributed computing with advice: information sensitivity of graph coloring
- Large cuts with local algorithms on triangle-free graphs
- Local 7-coloring for planar subgraphs of unit disk graphs
- Locality and checkability in wait-free computing
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- New techniques and tighter bounds for local computation algorithms
- Property testing of planarity in the \textsf{CONGEST} model
- A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
- Distributed minimum vertex coloring and maximum independent set in chordal graphs
- Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
- Distributed graph problems through an automata-theoretic lens
- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
- Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
- Hypergraph-based irregular application locality optimization
- Tight bounds for parallel randomized load balancing
- Constructing near spanning trees with few local inspections
- On the complexity of distributed graph coloring with local minimality constraints
- Trading bit, message, and time complexity of distributed algorithms
- Combinatorial algorithms for distributed graph coloring
- Locality and checkability in wait-free computing
- Broadcasting in an Unreliable SINR Model.
- Fast distributed approximation for TAP and 2-edge-connectivity
- Constant space and non-constant time in distributed computing
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
- Exact bounds for distributed graph colouring
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- Randomized OBDD-based graph algorithms
- Fast Distributed Approximations in Planar Graphs
- Local Maps: New Insights into Mobile Agent Algorithms
- Leveraging Linial’s Locality Limit
- Minimum entropy combinatorial optimization problems
- Distributed minimum dominating set approximations in restricted families of graphs
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- On the time and the bit complexity of distributed randomised anonymous ring colouring
- Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
- Symmetry breaking depending on the chromatic number or the neighborhood growth
- Checking Global Graph Properties by Means of Local Computations: the Majority Problem
- Local-Global Phenomena in Graphs
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- Delay and cooperation in nonstochastic bandits
- A time hierarchy theorem for the LOCAL model
- Distributed Colouring and Communication in Rings with Local Knowledge
- Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
- Distributed Dominating Set Approximations beyond Planar Graphs
- Distributed spanner approximation
- On the probe complexity of local computation algorithms
- A two-sided error distributed property tester for conductance
- Improved dynamic graph coloring
- Introduction to local certification
This page was built for publication: Locality in Distributed Graph Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3990110)
