Parallel Symmetry-Breaking in Sparse Graphs
From MaRDI portal
Recommendations
- Removing randomness in parallel computation without a processor penalty
- A new technique for distributed symmetry breaking
- scientific article; zbMATH DE number 139775
- Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees
- scientific article; zbMATH DE number 219240
Cited in
(58)- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- A fast and efficient NC algorithm for maximal matching
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- An optimal maximal independent set algorithm for bounded-independence graphs
- On the probe complexity of local computation algorithms
- On the microscopic view of time and messages
- Fast deterministic distributed algorithms for sparse spanners
- Combinatorial algorithms for distributed graph coloring
- Distributed algorithms for random graphs
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Making local algorithms wait-free: the case of ring coloring
- Maintaining dynamic sequences under equality tests in polylogarithmic time
- Local Hadwiger's conjecture
- Distributed algorithms for fractional coloring
- A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
- A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
- Parallel algorithms with optimal speedup for bounded treewidth
- Combinatorial algorithms for distributed graph coloring
- Optimal symmetry breaking for graph problems
- Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
- Distributed coloring in sparse graphs with fewer colors
- Optimal parallel algorithms on planar graphs
- More Efficient Parallel Integer Sorting
- Exact bounds for distributed graph colouring
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Efficient computation of implicit representations of sparse graphs
- On the effectiveness of symmetry breaking
- A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- Pairings and related symmetry notions
- Best of two local models: centralized local and distributed local algorithms
- Optimal parallel 3-coloring algorithm for rooted trees and its applications
- Property testing of planarity in the \textsf{CONGEST} model
- Low diameter graph decompositions
- Graph theoretical issues in computer networks
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- An optimal parallel algorithm for minimum spanning trees in planar graphs
- Exponential speedup over locality in \textsf{MPC} with optimal memory
- Distributed minimum vertex coloring and maximum independent set in chordal graphs
- Group graphs and computational symmetry on massively parallel architecture
- Descriptive complexity for distributed computing with circuits
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
- Fast algorithms for Vizing's theorem on bounded degree graphs
- An efficient distributed algorithm for constructing small dominating sets
- Borel Vizing's theorem for graphs of subexponential growth
- The power of multi-step Vizing chains
- o(log4 n) time parallel maximal matching algorithm using linear number of processors
- Neighborhood graphs and distributed Δ+1-coloring
- Distributed graph problems through an automata-theoretic lens
- Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
- scientific article; zbMATH DE number 7559119 (Why is no real title available?)
- Improved dynamic graph coloring
- Some simple distributed algorithms for sparse networks
- Borel versions of the local lemma and local algorithms for graphs of finite asymptotic separation index
- An efficient parallel algorithm for computing a large independent set in a planar graph
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
This page was built for publication: Parallel Symmetry-Breaking in Sparse Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3824434)
