Deterministic coin tossing with applications to optimal parallel list ranking
From MaRDI portal
Publication:3753489
Recommendations
Cited in
(only showing first 100 items - show all)- Deterministic compression with uncertain priors
- Designing checkers for programs that run in parallel
- Efficient quantum algorithms for simulating sparse Hamiltonians
- List-ranking on interconnection networks.
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- Faster optimal parallel prefix sums and list ranking
- Parallel algorithms for Burrows-Wheeler compression and decompression
- Best of two local models: centralized local and distributed local algorithms
- Distributed algorithms for weighted problems in sparse graphs
- Space-Efficient Euler Partition and Bipartite Edge Coloring
- Parallel algorithms with optimal speedup for bounded treewidth
- Improved nonconservative sequential and parallel integer sorting
- Optimal parallel algorithms on planar graphs
- Optimal merging and sorting on the EREW PRAM
- Breadth-first traversal of trees and integer sorting in parallel
- The power of multimedia: Combining point-to-point and multi-access networks
- scientific article; zbMATH DE number 1444289 (Why is no real title available?)
- Improved parallel integer sorting without concurrent writing
- Fast integer merging on the EREW PRAM
- Distributed algorithms for random graphs
- Towards optimal parallel bucket sorting
- An optimal parallel algorithm for minimum spanning trees in planar graphs
- Processor-efficient implementation of a maximum flow algorithm
- Fast integer merging on the EREW PRAM
- scientific article; zbMATH DE number 4064468 (Why is no real title available?)
- Counting clique trees and computing perfect elimination schemes in parallel
- Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees
- Parallel complexity of partitioning a planar graph into vertex-induced forests
- Selecting distances in the plane
- Sorting in linear time?
- Local Hadwiger's conjecture
- Distributed \((\varDelta + 1)\)-coloring in the physical model
- Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
- Combinatorial algorithms for distributed graph coloring
- Deterministic parallel list ranking
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Efficient computation of implicit representations of sparse graphs
- Classification of distributed binary labeling problems
- Efficient parallel term matching and anti-unification
- Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
- Oblivious algorithms for multicores and networks of processors
- An efficient distributed algorithm for constructing small dominating sets
- An optimally efficient selection algorithm
- Deterministic local algorithms, unique identifiers, and fractional graph colouring
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- Fast deterministic distributed algorithms for sparse spanners
- Parallel construction of a suffix tree with applications
- Parallel recognition of series-parallel graphs
- An optimal maximal independent set algorithm for bounded-independence graphs
- Efficient parallel algorithms for shortest paths in planar graphs
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- Hybridsort revisited and parallelized
- Locality and checkability in wait-free computing
- Constant-time local computation algorithms
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- A time hierarchy theorem for the LOCAL model
- A unified approach to parallel depth-first traversals of general trees
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- Coloring unstructured radio networks
- More general parallel tree contraction: Register allocation and broadcasting in a tree
- Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs
- Expected parallel time and sequential space complexity of graph and digraph problems
- Maintaining dynamic sequences under equality tests in polylogarithmic time
- An optimal parallel algorithm for maximal matching
- Improved deterministic parallel integer sorting
- scientific article; zbMATH DE number 4092762 (Why is no real title available?)
- Text sparsification via local maxima.
- Distributed computing in the asynchronous LOCAL model
- Making local algorithms wait-free: the case of ring coloring
- Distributed graph problems through an automata-theoretic lens
- Improved dynamic graph coloring
- Latency, capacity, and distributed minimum spanning trees
- Transversal partitioning in balanced hypergraphs
- Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
- A distributed algorithm for directed minimum-weight spanning tree
- Optimal distributed covering algorithms
- The role of a-priori information in networks of rational agents
- More general parallel tree contraction: register allocation and broadcasting in a tree
- Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
- Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
- Combinatorial algorithms for distributed graph coloring
- Sequential random permutation, list contraction and tree contraction are highly parallel
- Almost global problems in the LOCAL model
- Property testing of planarity in the \textsf{CONGEST} model
- Locality and checkability in wait-free computing
- Almost global problems in the LOCAL model
- Distributed graph problems through an automata-theoretic Lens
- An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs
- Efficient parallel modular decomposition (extended abstract)
- Neighborhood graphs and distributed Δ+1-coloring
- Edit distance with block operations
- TIME AND ENERGY OPTIMAL LIST RANKING ALGORITHMS ON THE k-CHANNEL BROADCAST COMMUNICATION MODEL WITH NO COLLISION DETECTION
- Space-efficient informational redundancy
- Concurrent disjoint set union
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- Efficient list ranking on the reconfigurable mesh, with applications
- Distributed minimum vertex coloring and maximum independent set in chordal graphs
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
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)
