Deterministic coin tossing with applications to optimal parallel list ranking
From MaRDI portal
(Redirected from Publication:3753489)
Recommendations
Cited in
(only showing first 100 items - show all)- Sequential random permutation, list contraction and tree contraction are highly parallel
- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
- Counting clique trees and computing perfect elimination schemes in parallel
- A time hierarchy theorem for the LOCAL model
- Space-Efficient Euler Partition and Bipartite Edge Coloring
- A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
- Locally-iterative (+1)-coloring in sublinear (in ) rounds
- Transversal partitioning in balanced hypergraphs
- Deterministic parallel list ranking
- Efficient parallel algorithms for shortest paths in planar graphs
- Oblivious algorithms for multicores and networks of processors
- Almost global problems in the LOCAL model
- Hybridsort revisited and parallelized
- NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems
- Deterministic compression with uncertain priors
- Locally consistent parsing for text indexing in small space
- More general parallel tree contraction: register allocation and broadcasting in a tree
- 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
- Introduction to local certification
- More efficient parallel flow algorithms
- Towards optimal parallel bucket sorting
- Parallel algorithms for Burrows-Wheeler compression and decompression
- scientific article; zbMATH DE number 4092762 (Why is no real title available?)
- Fast deterministic distributed algorithms for sparse spanners
- Combinatorial algorithms for distributed graph coloring
- An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs
- Distributed algorithms for weighted problems in sparse graphs
- Text sparsification via local maxima.
- Distributed algorithms for random graphs
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Making local algorithms wait-free: the case of ring coloring
- Fast integer merging on the EREW PRAM
- 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
- Fast integer merging on the EREW PRAM
- Local Hadwiger's conjecture
- Latency, capacity, and distributed minimum spanning trees
- Processor-efficient implementation of a maximum flow algorithm
- Parallel algorithms with optimal speedup for bounded treewidth
- Combinatorial algorithms for distributed graph coloring
- Edit distance with block operations
- scientific article; zbMATH DE number 4064468 (Why is no real title available?)
- More general parallel tree contraction: Register allocation and broadcasting in a tree
- Designing checkers for programs that run in parallel
- Coloring unstructured radio networks
- Improved parallel integer sorting without concurrent writing
- Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
- Fast and fair randomized wait-free locks
- Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs
- 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
- List-ranking on interconnection networks.
- Exact bounds for distributed graph colouring
- Parallel recognition of series-parallel graphs
- Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
- Efficient computation of implicit representations of sparse graphs
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- Periodic colorings and orientations in infinite graphs
- Parallel complexity of partitioning a planar graph into vertex-induced forests
- Selecting distances in the plane
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- Classification of distributed binary labeling problems
- TIME AND ENERGY OPTIMAL LIST RANKING ALGORITHMS ON THE k-CHANNEL BROADCAST COMMUNICATION MODEL WITH NO COLLISION DETECTION
- Parallel construction of a suffix tree with applications
- Sensitivity analysis of the maximum matching problem
- Locality and checkability in wait-free computing
- The role of a-priori information in networks of rational agents
- Locality and checkability in wait-free computing
- Best of two local models: centralized local and distributed local algorithms
- Distributed \((\varDelta + 1)\)-coloring in the physical model
- Property testing of planarity in the \textsf{CONGEST} model
- Efficient parallel modular decomposition (extended abstract)
- scientific article; zbMATH DE number 1444289 (Why is no real title available?)
- An optimal parallel algorithm for maximal matching
- Deterministic local algorithms, unique identifiers, and fractional graph colouring
- Sorting in linear time?
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- Almost global problems in the LOCAL model
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- Locally computing edge orientations
- Distributed graph problems through an automata-theoretic Lens
- Breadth-first traversal of trees and integer sorting in parallel
- Local distributed rounding: generalized to MIS, matching, set cover, and beyond
- Faster optimal parallel prefix sums and list ranking
- Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
- Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
- An optimal parallel algorithm for minimum spanning trees in planar graphs
- Fast deterministic rendezvous in labeled lines
- Exponential speedup over locality in \textsf{MPC} with optimal memory
- Distributed minimum vertex coloring and maximum independent set in chordal graphs
- Descriptive complexity for distributed computing with circuits
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
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)
