- Parallel Graph Connectivity in Log Diameter Rounds
2018/05/08 by Alexandr Andoni, Clifford Stein, Andoni, Alexandr +7 · 1 citation
Computer Science · Mathematics · #Algorithm #Binary logarithm #Bottleneck #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Data Structures and Algorithms (cs.DS) #Discrete mathematics #Distributed #FOS: Computer and information sciences #Graph #Interconnection Networks and Systems #Log-log plot #Mathematics #Parallel #Parallel Computing and Optimization Techniques #Scalability #Spanning tree #Time complexity #Upper and lower bounds #and Cluster Computing (cs.DC) #cs.DC #cs.DS
- Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
2018/04/12 by David G. Harris, Johannes Schneider, Hsin-Hao Su · 5 citations
Computer Science · Mathematics · #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Cryptography and Data Security #Discrete mathematics #Graph #Graph coloring #Log-log plot #Matching (statistics) #Mathematics #Optimization and Search Problems #Randomized algorithm
- Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time
2017/01/01 by Shang-En Huang, Dawei Huang, Tsvi Kopelowitz +1 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Distributed systems and fault tolerance #Binary logarithm #Log-log plot #Combinatorics #Amortized analysis #Mathematics #Graph #Upper and lower bounds #Data structure #Discrete mathematics #Computer science
- The Locality of Distributed Symmetry Breaking
2016/06/28 by Leonid Barenboim, Michael Elkin, Seth Pettie +1 · 23 citations
Computer Science · Mathematics · #Algorithm #Arboricity #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Cryptography and Data Security #Degeneracy (biology) #Discrete mathematics #Graph #Log-log plot #Matching (statistics) #Mathematics #Optimization and Search Problems #Planar graph #Running time #Time complexity #Upper and lower bounds #Vertex (graph theory)
- Faster Deterministic Fully-Dynamic Graph Connectivity
2013/01/06 by Christian Wulff‐Nilsen · 1 citation
Computer Science · Mathematics · #Error Correcting Code Techniques #Complexity and Algorithms in Graphs #Caching and Content Delivery #Combinatorics #Binary logarithm #Computer science #Graph #Data structure #Time complexity #Log-log plot #Amortized analysis #Discrete mathematics #Mathematics #Algorithm
- A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates
2005/01/01 by Kazuyuki Amano, Akira Maruoka · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Machine Learning and Algorithms #Clique #Mathematics #Negation #Combinatorics #Binary logarithm #Log-log plot #Upper and lower bounds #Function (biology) #Discrete mathematics #Computer science
- Approximating Maximum Clique by Removing Subgraphs
2004/01/01 by Uriel Feige · 4 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Combinatorics #Mathematics #Clique #Log-log plot #Clique number #Binary logarithm #Clique graph #Graph #Approximation algorithm #Discrete mathematics #Constant (computer programming) #Line graph #Computer science #Graph power
- Noise-tolerant learning, the parity problem, and the statistical query model
2003/07/01 by Avrim Blum, Adam Kalai, Adam Tauman Kalai +1 · 52 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Binary logarithm #Code word #Combinatorics #Complexity and Algorithms in Graphs #Decoding methods #Discrete mathematics #Log-log plot #Machine Learning and Algorithms #Mathematics #Parity (physics) #Statistical model #Statistics #Time complexity #Tuple
- Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring
2001/01/01 by Subhash Khot · 5 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Combinatorics #Binary logarithm #Graph #Log-log plot #Mathematics #Clique number #Graph coloring #Constant (computer programming) #Time complexity #Approximation algorithm #Clique #Upper and lower bounds #Discrete mathematics #Computer science
- Efficient computation of implicit representations of sparse graphs
1997/10/01 by Srinivasa R. Arikati, Anil Maheshwari, Christos Zaroliagis +1 · 1 citation
Computer Science · Mathematics · #Adjacency list #Advanced Graph Theory Research #Algorithm #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computation #Discrete mathematics #Graph #Interconnection Networks and Systems #Log-log plot #Mathematics #Parallel algorithm #Time complexity #Vertex (graph theory)
- RANDOMIZED PARALLEL ALGORITHMS FOR TRAPEZOIDAL DIAGRAMS
1992/06/01 by Kenneth L. Clarkson, Richard Cole, Robert E. Tarjan · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Combinatorial Mathematics #Data Management and Algorithms #Binary logarithm #Log-log plot #Mathematics #Combinatorics #Randomized algorithm #Algorithm #Parallel algorithm #Deterministic algorithm #Set (abstract data type) #Time complexity #Efficient algorithm #Discrete mathematics #Computer science
- Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments
1990/02/01 by Amotz Bar-Noy, Joseph Naor · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Binary logarithm #Combinatorics #Computer science #Discrete mathematics #Graph #Hamiltonian path #Limits and Structures in Graph Theory #Log-log plot #Mathematics #Path (computing) #Set (abstract data type) #Sorting #Sorting algorithm #Tournament #semigroups and automata theory
- Parallel Merge Sort
1988/08/01 by Richard Cole · 7 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Constant (computer programming) #Database #Log-log plot #Mathematics #Merge (version control) #Merge algorithm #Merge sort #Parallel algorithm #Parallel computing #Programming language #Running time #Sorting algorithm #sort
- Randomized speed-ups in parallel computation
1984/01/01 by Uzi Vishkin · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Advanced Graph Theory Research #Binary logarithm #Conjecture #Randomized algorithm #Parallel algorithm #Computer science #Computation #Parallel computing #Time complexity #Deterministic algorithm #Log-log plot #Algorithm #Speedup #Combinatorics #Running time #Mathematics #Discrete mathematics
- On computing the length of longest increasing subsequences
1975/01/01 by Michael L. Fredman · 2 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Binary logarithm #Combinatorics #Computer science #Data Management and Algorithms #Discrete mathematics #Log-log plot #Mathematics #Optimization and Search Problems #Sequence (biology) #Set (abstract data type) #Time complexity