Locality in Distributed Graph Algorithms
From MaRDI portal
Publication:3990110
DOI10.1137/0221015zbMath0787.05058OpenAlexW2054910423WikidataQ55896380 ScholiaQ55896380MaRDI QIDQ3990110
Publication date: 28 June 1992
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/3f084898e62b5824cf70100b91a63f1c2450a467
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Theory of computing (68Q99)
Related Items (only showing first 100 items - show all)
Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information ⋮ Neighborhood graphs and distributed Δ+1-coloring ⋮ Fast Distributed Approximation for Max-Cut ⋮ Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs ⋮ Exact Bounds for Distributed Graph Colouring ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Randomized OBDD-Based Graph Algorithms ⋮ Local-Global Phenomena in Graphs ⋮ Constant space and non-constant time in distributed computing ⋮ Broadcasting in an Unreliable SINR Model. ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ Find Your Place: Simple Distributed Algorithms for Community Detection ⋮ Local deal-agreement algorithms for load balancing in dynamic general graphs ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Locally checkable problems in rooted trees ⋮ Brief announcement: Distributed reconfiguration of spanning trees ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ Distributed computing with the Cloud ⋮ Component stability in low-space massively parallel computation ⋮ Distributed half-integral matching and beyond ⋮ Exact distributed sampling ⋮ Bounds and algorithms for generalized superimposed codes ⋮ A note on the network coloring game: a randomized distributed \((\Delta+1)\)-coloring algorithm ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Unnamed Item ⋮ Distributed half-integral matching and beyond ⋮ About informatics, distributed computing, and our job: a personal view ⋮ Distributed coloring of hypergraphs ⋮ Unnamed Item ⋮ Theory of graph neural networks: representation and learning ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ Distributed MIS with Low Energy and Time Complexities ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ Brief Announcement: Local Problems in the SUPPORTED Model ⋮ A Near-Optimal Deterministic Distributed Synchronizer ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Constructing near spanning trees with few local inspections ⋮ Simple Neural-Like P Systems for Maximal Independent Set Selection ⋮ Deterministic compression with uncertain priors ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Local Maps: New Insights into Mobile Agent Algorithms ⋮ Leveraging Linial’s Locality Limit ⋮ Some simple distributed algorithms for sparse networks ⋮ An efficient distributed algorithm for constructing small dominating sets ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ Minimum Entropy Combinatorial Optimization Problems ⋮ What Can be Computed in a Distributed System? ⋮ Unnamed Item ⋮ LOCAL CONSTRUCTION AND COLORING OF SPANNERS OF LOCATION AWARE UNIT DISK GRAPHS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs ⋮ On the complexity of distributed graph coloring with local minimality constraints ⋮ Unnamed Item ⋮ How long it takes for an ordinary node with an ordinary ID to output? ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Local approximation of the maximum cut in regular graphs ⋮ Weak models of distributed computing, with connections to modal logic ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Making local algorithms wait-free: the case of ring coloring ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ A topological perspective on distributed network algorithms ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Distributed MST for constant diameter graphs ⋮ The Impact of Locality in the Broadcast Congested Clique Model ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ Equilibria of Games in Networks for Local Tasks ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Trading Bit, Message, and Time Complexity of Distributed Algorithms ⋮ Combinatorial Algorithms for Distributed Graph Coloring ⋮ Locality and Checkability in Wait-Free Computing ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Distributed Reconfiguration of Maximal Independent Sets ⋮ An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract) ⋮ Almost global problems in the LOCAL model ⋮ Distributed Spanner Approximation ⋮ Fast Distributed Approximations in Planar Graphs ⋮ Checking Global Graph Properties by Means of Local Computations: the Majority Problem ⋮ Improved Dynamic Graph Coloring ⋮ Unnamed Item ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Unnamed Item ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Introduction to local certification ⋮ Computing roots of graphs is hard
This page was built for publication: Locality in Distributed Graph Algorithms
