Deterministic coin tossing with applications to optimal parallel list ranking
From MaRDI portal
Publication:3753489
DOI10.1016/S0019-9958(86)80023-7zbMath0612.68044OpenAlexW2067661972WikidataQ55896379 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
Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications, Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique, 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, Fast Distributed Approximations in Planar Graphs, Improved Dynamic Graph Coloring, Deterministic parallel list ranking, Introduction to local certification, An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs, Distributed graph problems through an automata-theoretic Lens
