Parallel Symmetry-Breaking in Sparse Graphs
From MaRDI portal
Publication:3824434
DOI10.1137/0401044zbMath0671.05038OpenAlexW2169102947WikidataQ55966484 ScholiaQ55966484MaRDI QIDQ3824434
Andrew V. Goldberg, Gregory E. Shannon, Serge A. Plotkin
Publication date: 1988
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://docs.lib.purdue.edu/cstech/614
graph coloringplanar graphsrooted treesmaximal independent setbreaking symmetry in parallelconstant genusgraphs ofgraphs of constant degree
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items
Neighborhood graphs and distributed Δ+1-coloring, The local nature of \(\Delta\)-coloring and its algorithmic applications, 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, Exact Bounds for Distributed Graph Colouring, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs, A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH, o(log4 n) time parallel maximal matching algorithm using linear number of processors, Property testing of planarity in the \textsf{CONGEST} model, Efficient computation of implicit representations of sparse graphs, A fast distributed algorithm for \((\Delta+1)\)-edge-coloring, Distributed minimum vertex coloring and maximum independent set in chordal graphs, Distributed algorithms for random graphs, Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms, Unnamed Item, Local Hadwiger's conjecture, Distributed graph problems through an automata-theoretic lens, Toward more localized local algorithms: removing assumptions concerning global knowledge, Some simple distributed algorithms for sparse networks, An efficient distributed algorithm for constructing small dominating sets, Fast deterministic distributed algorithms for sparse spanners, Optimal parallel 3-coloring algorithm for rooted trees and its applications, Maintaining dynamic sequences under equality tests in polylogarithmic time, Parallel algorithms with optimal speedup for bounded treewidth, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, Pairings and related symmetry notions, Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, Combinatorial algorithms for distributed graph coloring, Unnamed Item, Optimal parallel algorithms on planar graphs, Best of two local models: centralized local and distributed local algorithms, On the Microscopic View of Time and Messages, An optimal maximal independent set algorithm for bounded-independence graphs, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition, Improved distributed algorithms for coloring interval graphs with application to multicoloring trees, More Efficient Parallel Integer Sorting, Making local algorithms wait-free: the case of ring coloring, Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs, Combinatorial Algorithms for Distributed Graph Coloring, A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths, Distributed coloring in sparse graphs with fewer colors, Improved Dynamic Graph Coloring, Low diameter graph decompositions, An efficient parallel algorithm for computing a large independent set in a planar graph, Graph theoretical issues in computer networks, Distributed algorithms for fractional coloring
