Deterministic coin tossing with applications to optimal parallel list ranking
From MaRDI portal
DOI10.1016/S0019-9958(86)80023-7zbMATH Open0612.68044DBLPjournals/iandc/ColeV86OpenAlexW2067661972WikidataQ55896379 ScholiaQ55896379MaRDI QIDQ3753489FDOQ3753489
Publication date: 1986
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(86)80023-7
Cited In (only showing first 100 items - show all)
- Locally checkable problems in rooted trees
- More efficient parallel flow algorithms
- Introduction to local certification
- Title not available (Why is that?)
- An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Dynamic networks of finite state machines
- Text sparsification via local maxima.
- Making local algorithms wait-free: the case of ring coloring
- Latency, capacity, and distributed minimum spanning trees
- A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation
- Combinatorial Algorithms for Distributed Graph Coloring
- Improved Dynamic Graph Coloring
- TIME AND ENERGY OPTIMAL LIST RANKING ALGORITHMS ON THE k-CHANNEL BROADCAST COMMUNICATION MODEL WITH NO COLLISION DETECTION
- Locality and checkability in wait-free computing
- Property testing of planarity in the \textsf{CONGEST} model
- Efficient parallel modular decomposition (extended abstract)
- How long it takes for an ordinary node with an ordinary ID to output?
- Almost global problems in the LOCAL model
- Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
- Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
- Distributed graph problems through an automata-theoretic Lens
- Exact Bounds for Distributed Graph Colouring
- Distributed minimum vertex coloring and maximum independent set in chordal graphs
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
- Efficient list ranking on the reconfigurable mesh, with applications
- Concurrent disjoint set union
- On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition
- Distributed computing in the asynchronous LOCAL model
- 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
- A distributed algorithm for directed minimum-weight spanning tree
- Optimal distributed covering algorithms
- Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
- Title not available (Why is that?)
- Space-efficient informational redundancy
- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
- Leveraging multiple channels in ad hoc networks
- NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems
- Transversal partitioning in balanced hypergraphs
- More general parallel tree contraction: register allocation and broadcasting in a tree
- Almost global problems in the LOCAL model
- An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs
- An optimally efficient selection algorithm
- Improved deterministic parallel integer sorting
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees
- Efficient parallel term matching and anti-unification
- An optimal maximal independent set algorithm for bounded-independence graphs
- Parallel algorithms for Burrows-Wheeler compression and decompression
- Towards optimal parallel bucket sorting
- Combinatorial algorithms for distributed graph coloring
- Fast deterministic distributed algorithms for sparse spanners
- Distributed algorithms for weighted problems in sparse graphs
- Distributed algorithms for random graphs
- Fast integer merging on the EREW PRAM
- Fast integer merging on the EREW PRAM
- Local Hadwiger's conjecture
- A unified approach to parallel depth-first traversals of general trees
- Maintaining dynamic sequences under equality tests in polylogarithmic time
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Parallel algorithms with optimal speedup for bounded treewidth
- Processor-efficient implementation of a maximum flow algorithm
- Title not available (Why is that?)
- Coloring unstructured radio networks
- More general parallel tree contraction: Register allocation and broadcasting in a tree
- Designing checkers for programs that run in parallel
- Improved parallel integer sorting without concurrent writing
- Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
- Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs
- List-ranking on interconnection networks.
- Optimal parallel algorithms on planar graphs
- Optimal merging and sorting on the EREW PRAM
- The power of multimedia: Combining point-to-point and multi-access networks
- Parallel recognition of series-parallel graphs
- A Time Hierarchy Theorem for the LOCAL Model
- Efficient computation of implicit representations of sparse graphs
- Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- Parallel complexity of partitioning a planar graph into vertex-induced forests
- Selecting distances in the plane
- Classification of distributed binary labeling problems
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- Parallel construction of a suffix tree with applications
- Best of two local models: centralized local and distributed local algorithms
- Distributed \((\varDelta + 1)\)-coloring in the physical model
- Title not available (Why is that?)
- An optimal parallel algorithm for maximal matching
- Deterministic local algorithms, unique identifiers, and fractional graph colouring
- Sorting in linear time?
- Locality and Checkability in Wait-Free Computing
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- Faster optimal parallel prefix sums and list ranking
- Breadth-first traversal of trees and integer sorting in parallel
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- An efficient distributed algorithm for constructing small dominating sets
- Constant-time local computation algorithms
Recommendations
This page was built for publication: Deterministic coin tossing with applications to optimal parallel list ranking
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3753489)
