The probabilistic method yields deterministic parallel algorithms (Q1342858): Difference between revisions

@@ Property / cites work @@
+A fast and simple randomized parallel algorithm for the maximal independent set problem
+Normal rank
@@ Property / cites work @@
+An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
+Normal rank
@@ Property / cites work @@
+Balanced two-colorings of finite sets in the cube
@@ Property / cites work: Balanced two-colorings of finite sets in the cube / rank @@
+Normal rank
@@ Property / cites work @@
+``Integer-making'' theorems
@@ Property / cites work: ``Integer-making'' theorems / rank @@
+Normal rank
@@ Property / cites work @@
+Simulating (log             <sup>c</sup>             <i>n</i>             )-wise independence in NC
+Normal rank
@@ Property / cites work @@
+A deterministic view of random sampling and its use in geometry
+Normal rank
@@ Property / cites work @@
+A Randomized Algorithm for Closest-Point Queries
@@ Property / cites work: A Randomized Algorithm for Closest-Point Queries / rank @@
+Normal rank
@@ Property / cites work @@
+New applications of random sampling in computational geometry
+Normal rank
@@ Property / cites work @@
+On a combinatorial game
@@ Property / cites work: On a combinatorial game / rank @@
+Normal rank
@@ Property / cites work @@
+Q5541610
@@ Property / cites work: Q5541610 / rank @@
+Normal rank
@@ Property / cites work @@
+NP completeness of finding the chromatic index of regular graphs
+Normal rank
@@ Property / cites work @@
+The NP-Completeness of Edge-Coloring
@@ Property / cites work: The NP-Completeness of Edge-Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+\(\epsilon\)-nets and simplex range queries
@@ Property / cites work: \(\epsilon\)-nets and simplex range queries / rank @@
+Normal rank
@@ Property / cites work @@
+Derandomization through approximation
@@ Property / cites work: Derandomization through approximation / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient parallel algorithms for edge coloring problems
+Normal rank
@@ Property / cites work @@
+Constructing a perfect matching is in random NC
@@ Property / cites work: Constructing a perfect matching is in random NC / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of parallel search
@@ Property / cites work: The complexity of parallel search / rank @@
+Normal rank
@@ Property / cites work @@
+A fast parallel algorithm for the maximal independent set problem
+Normal rank
@@ Property / cites work @@
+A fast parallel algorithm for routing in permutation networks
+Normal rank
@@ Property / cites work @@
+On the ratio of optimal integral and fractional covers
+Normal rank
@@ Property / cites work @@
+A Simple Parallel Algorithm for the Maximal Independent Set Problem
+Normal rank
@@ Property / cites work @@
+Q4146667
@@ Property / cites work: Q4146667 / rank @@
+Normal rank
@@ Property / cites work @@
+A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
+Normal rank
@@ Property / cites work @@
+Matching is as easy as matrix inversion
@@ Property / cites work: Matching is as easy as matrix inversion / rank @@
+Normal rank
@@ Property / cites work @@
+Small-Bias Probability Spaces: Efficient Constructions and Applications
+Normal rank
@@ Property / cites work @@
+Balancing families of sets
@@ Property / cites work: Balancing families of sets / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic construction of deterministic algorithms: approximating packing integer programs
+Normal rank
@@ Property / cites work @@
+Q3484356
@@ Property / cites work: Q3484356 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3481743
@@ Property / cites work: Q3481743 / rank @@
+Normal rank
@@ Property / cites work @@
+Six Standard Deviations Suffice
@@ Property / cites work: Six Standard Deviations Suffice / rank @@
+Normal rank
@@ Property / cites work @@
+Balancing vectors in the max norm
@@ Property / cites work: Balancing vectors in the max norm / rank @@
+Normal rank