Locality in Distributed Graph Algorithms
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Constructing near spanning trees with few local inspections
- Equilibria of Games in Networks for Local Tasks
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- Brief announcement: Distributed reconfiguration of spanning trees
- Symmetry breaking depending on the chromatic number or the neighborhood growth
- Local construction and coloring of spanners of location aware unit disk graphs
- Fast distributed approximation for TAP and 2-edge-connectivity
- Component stability in low-space massively parallel computation
- Distributed computing with the Cloud
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- An optimal maximal independent set algorithm for bounded-independence graphs
- Introduction to local certification
- Fast Distributed Approximation for Max-Cut
- Complexity analysis of a decentralised graph colouring algorithm
- On the probe complexity of local computation algorithms
- Linial for lists
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- The complexity landscape of distributed locally checkable problems on trees
- Distributed independent sets in interval and segment intersection graphs
- A topological perspective on distributed network algorithms
- A hierarchy of local decision
- Fast deterministic distributed algorithms for sparse spanners
- Combinatorial algorithms for distributed graph coloring
- Distributed algorithms for weighted problems in sparse graphs
- On the relationship between continuous- and discrete-time quantum walk
- scientific article; zbMATH DE number 7561635 (Why is no real title available?)
- A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
- Weak models of distributed computing, with connections to modal logic
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Distributed Computing with the Cloud
- Linear-time algorithms for tree root problems
- Minimum entropy combinatorial optimization problems
- Fooling views: a new lower bound technique for distributed computations under congestion
- Allowing each node to communicate only once in a distributed system: shared whiteboard models
- Asynchronous self-stabilization made fast, simple, and energy-efficient
- Adaptive massively parallel coloring in sparse graphs
- (+1) vertex coloring in O(n) communication
- Brief announcement: Low-distortion clustering in bounded growth graphs
- Universally optimal information dissemination and shortest paths in the HYBRID distributed model
- Completing the node-averaged complexity landscape of LCLs on trees
- A LOCAL view of the polynomial hierarchy
- Brief announcement: Local advice and local decompression
- A tight lower bound for 3-coloring grids in the online-LOCAL model
- Making local algorithms wait-free: the case of ring coloring
- Making local algorithms wait-free: the case of ring coloring
- Minimum entropy combinatorial optimization problems
- Distributed independent sets in interval and segment intersection graphs
- Local MST computation with short advice
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Local 7-coloring for planar subgraphs of unit disk graphs
- Distributed algorithms for fractional coloring
- Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge
- A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
- Simple neural-like P systems for maximal independent set selection
- Distributed half-integral matching and beyond
- Exact distributed sampling
- Derandomizing local distributed algorithms under bandwidth restrictions
- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
- On the extremal combinatorics of the Hamming space
- Combinatorial algorithms for distributed graph coloring
- Distributed broadcast in radio networks of unknown topology.
- Exact leaf powers
- A faster distributed protocol for constructing a minimum spanning tree
- Constant space and non-constant time in distributed computing
- Tight bounds for parallel randomized load balancing
- Coloring unstructured radio networks
- A fast network-decomposition algorithm and its applications to constant-time distributed computation
- A distributed low tree-depth decomposition algorithm for bounded expansion classes
- Distributed Colouring and Communication in Rings with Local Knowledge
- Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
- ( + 1) vertex coloring in O(n) communication
- Distributed coloring in sparse graphs with fewer colors
- Computing roots of graphs is hard
- A simple local 3-approximation algorithm for vertex cover
- Broadcasting in an Unreliable SINR Model.
- Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels.
- Distributed spanner approximation
- Local approximation of the maximum cut in regular graphs
- Design patterns in beeping algorithms: examples, emulation, and analysis
- Exact bounds for distributed graph colouring
- A two-sided error distributed property tester for conductance
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
- Distributed algorithms for the Lovász local lemma and graph coloring
- Distributed coloring and the local structure of unit-disk graphs
- Distributed MST for constant diameter graphs
- The topology of local computing in networks
- Trading bit, message, and time complexity of distributed algorithms
- Computable vs descriptive combinatorics of local problems on trees
- Networks cannot compute their diameter in sublinear time
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- Resource efficient stabilization for local tasks despite unknown capacity links
- Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
- No sublogarithmic-time approximation scheme for bipartite vertex cover
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- Classification of distributed binary labeling problems
- Parallel derandomization for coloring
- Local-Global Phenomena in Graphs
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)
