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
(59)- Optimal parallel 3-coloring algorithm for rooted trees and its applications
- Group graphs and computational symmetry on massively parallel architecture
- Low diameter graph decompositions
- Graph theoretical issues in computer networks
- A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
- Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
- A fast and efficient NC algorithm for maximal matching
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- Efficient computation of implicit representations of sparse graphs
- Best of two local models: centralized local and distributed local algorithms
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- Pairings and related symmetry notions
- Optimal symmetry breaking for graph problems
- Distributed algorithms for fractional coloring
- Combinatorial algorithms for distributed graph coloring
- Distributed coloring in sparse graphs with fewer colors
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- 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
- Combinatorial algorithms for distributed graph coloring
- Exact bounds for distributed graph colouring
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- An optimal parallel algorithm for minimum spanning trees in planar graphs
- Parallel algorithms with optimal speedup for bounded treewidth
- On the microscopic view of time and messages
- A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH
- o(log4 n) time parallel maximal matching algorithm using linear number of processors
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- On the probe complexity of local computation algorithms
- Improved dynamic graph coloring
- Neighborhood graphs and distributed Δ+1-coloring
- Distributed coloring of graphs with an optimal number of colors
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Some simple distributed algorithms for sparse networks
- An efficient distributed algorithm for constructing small dominating sets
- On the effectiveness of symmetry breaking
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- Optimal parallel algorithms on planar graphs
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
- Making local algorithms wait-free: the case of ring coloring
- More Efficient Parallel Integer Sorting
- Local Hadwiger's conjecture
- The power of multi-step Vizing chains
- Borel Vizing's theorem for graphs of subexponential growth
- Maintaining dynamic sequences under equality tests in polylogarithmic time
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Exponential speedup over locality in \textsf{MPC} with optimal memory
- Descriptive complexity for distributed computing with circuits
- Borel versions of the local lemma and local algorithms for graphs of finite asymptotic separation index
- Fast algorithms for Vizing's theorem on bounded degree graphs
- Distributed edge coloring in time polylogarithmic in \({\Delta }\)
- An efficient parallel algorithm for computing a large independent set in a planar graph
- Distributed algorithms for random graphs
- Fast deterministic distributed algorithms for sparse spanners
- An optimal maximal independent set algorithm for bounded-independence graphs
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
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)
