Deterministic coin tossing with applications to optimal parallel list ranking
From MaRDI portal
Publication:3753489
DOI10.1016/S0019-9958(86)80023-7zbMath0612.68044DBLPjournals/iandc/ColeV86OpenAlexW2067661972WikidataQ55896379 ScholiaQ55896379MaRDI QIDQ3753489
Uzi Vishkin, Richard John Cole
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
Related Items (only showing first 100 items - show all)
Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique ⋮ Efficient list ranking on the reconfigurable mesh, with applications ⋮ More efficient parallel flow algorithms ⋮ Classification of distributed binary labeling problems ⋮ More general parallel tree contraction: register allocation and broadcasting in a tree ⋮ Distributed computing in the asynchronous LOCAL model ⋮ Latency, capacity, and distributed minimum spanning trees ⋮ Space-Efficient Euler Partition and Bipartite Edge Coloring ⋮ Fast integer merging on the EREW PRAM ⋮ Selecting distances in the plane ⋮ An optimal parallel algorithm for maximal matching ⋮ Neighborhood graphs and distributed Δ+1-coloring ⋮ Coloring unstructured radio networks ⋮ Efficient parallel algorithms for shortest paths in planar graphs ⋮ The local nature of \(\Delta\)-coloring and its algorithmic applications ⋮ Towards optimal parallel bucket sorting ⋮ Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems ⋮ Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees ⋮ 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 ⋮ Parallel construction of a suffix tree with applications ⋮ The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time ⋮ An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs ⋮ Improved parallel integer sorting without concurrent writing ⋮ An optimally efficient selection algorithm ⋮ Designing checkers for programs that run in parallel ⋮ Distributed algorithms for weighted problems in sparse graphs ⋮ Transversal partitioning in balanced hypergraphs ⋮ Property testing of planarity in the \textsf{CONGEST} model ⋮ Efficient computation of implicit representations of sparse graphs ⋮ Hybridsort revisited and parallelized ⋮ Autoreducibility and mitoticity of logspace-complete sets for NP and other classes ⋮ Parallel complexity of partitioning a planar graph into vertex-induced forests ⋮ Efficient quantum algorithms for simulating sparse Hamiltonians ⋮ Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Distributed algorithms for random graphs ⋮ Locally checkable problems in rooted trees ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Leveraging multiple channels in ad hoc networks ⋮ Deterministic local algorithms, unique identifiers, and fractional graph colouring ⋮ Oblivious algorithms for multicores and networks of processors ⋮ NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems ⋮ Efficient parallel modular decomposition (extended abstract) ⋮ Text sparsification via local maxima. ⋮ Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms ⋮ Local Hadwiger's conjecture ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Optimal distributed covering algorithms ⋮ A distributed algorithm for directed minimum-weight spanning tree ⋮ Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022 ⋮ Unnamed Item ⋮ Parallel algorithms for Burrows-Wheeler compression and decompression ⋮ Fast integer merging on the EREW PRAM ⋮ Locality and checkability in wait-free computing ⋮ Improved nonconservative sequential and parallel integer sorting ⋮ Space-efficient informational redundancy ⋮ Deterministic compression with uncertain priors ⋮ Leveraging Linial’s Locality Limit ⋮ An efficient distributed algorithm for constructing small dominating sets ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ Improved deterministic parallel integer sorting ⋮ TIME AND ENERGY OPTIMAL LIST RANKING ALGORITHMS ON THE k-CHANNEL BROADCAST COMMUNICATION MODEL WITH NO COLLISION DETECTION ⋮ A unified approach to parallel depth-first traversals of general trees ⋮ Processor-efficient implementation of a maximum flow algorithm ⋮ Breadth-first traversal of trees and integer sorting in parallel ⋮ Expected parallel time and sequential space complexity of graph and digraph problems ⋮ Almost global problems in the LOCAL model ⋮ Constant-time local computation algorithms ⋮ Maintaining dynamic sequences under equality tests in polylogarithmic time ⋮ Parallel algorithms with optimal speedup for bounded treewidth ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Parallel recognition of series-parallel graphs ⋮ Efficient parallel term matching and anti-unification ⋮ Combinatorial algorithms for distributed graph coloring ⋮ Unnamed Item ⋮ Optimal parallel algorithms on planar graphs ⋮ Optimal merging and sorting on the EREW PRAM ⋮ Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs ⋮ The power of multimedia: Combining point-to-point and multi-access networks ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ How long it takes for an ordinary node with an ordinary ID to output? ⋮ 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 ⋮ Making local algorithms wait-free: the case of ring coloring ⋮ Dynamic networks of finite state machines ⋮ Distributed \((\varDelta + 1)\)-coloring in the physical model ⋮ Counting clique trees and computing perfect elimination schemes in parallel ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms ⋮ Combinatorial Algorithms for Distributed Graph Coloring ⋮ Locality and Checkability in Wait-Free Computing ⋮ Sorting in linear time? ⋮ More general parallel tree contraction: Register allocation and broadcasting in a tree ⋮ Concurrent disjoint set union ⋮ Characterizing multiterminal flow networks and computing flows in networks of small treewidth ⋮ Faster optimal parallel prefix sums and list ranking ⋮ Almost global problems in the LOCAL model
This page was built for publication: Deterministic coin tossing with applications to optimal parallel list ranking
