- Flipping Persuasively in Constant Time
1990/06/01 by Cynthia Dwork, David Shmoys, David B. Shmoys +1 · 1 citation
Computer Science · Mathematics · #Binary logarithm #Combinatorics #Computer science #Constant (computer programming) #Corollary #Cryptography and Data Security #Deterministic algorithm #Discrete mathematics #Distributed systems and fault tolerance #Generalization #Log-log plot #Mathematics #Privacy-Preserving Technologies in Data #Probabilistic logic #Randomized algorithm #Randomness #Statistics #Time complexity
- An O(nlog log n)-Time Algorithm for Triangulating a Simple Polygon
1988/02/01 by Robert E. Tarjan, Christopher J. Van Wyk · 10 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Optimization and Search Problems #Robotics and Sensor-Based Localization #Simple polygon #Combinatorics #Polygon covering #Diagonal #Mathematics #Polygon (computer graphics) #Partition (number theory) #Simple (philosophy) #Computational geometry #Time complexity #Binary logarithm #Vertex (graph theory) #Triangulation #Algorithm #SIMPLE algorithm #Sorting #Monotone polygon #Computer science #Graph #Geometry
- Applications of random sampling in computational geometry, II
1988/01/01 by Kenneth L. Clarkson · 5 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Point processes and geometric inequalities #Convex hull #Computational geometry #Mathematics #Combinatorics #Binary logarithm #Algorithm #Las vegas #Regular polygon #Point (geometry) #Plane (geometry) #Simple (philosophy) #Discrete mathematics #Sampling (signal processing) #Computer science #Geometry
- A fast planar partition algorithm. I
1988/01/01 by Ketan Mulmuley · 4 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Combinatorial Mathematics #Advanced Image and Video Retrieval Techniques #Partition (number theory) #Intersection (aeronautics) #Algorithm #Partition problem #Simple (philosophy) #Running time #Computer science #Combinatorics #Planar #Set (abstract data type) #Binary logarithm #Mathematics #Randomized algorithm #Discrete mathematics
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
1987/12/01 by Greg N. Federickson · 3 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Combinatorics #Mathematics #Shortest path problem #Binary logarithm #Algorithm #Time complexity #Maximum flow problem #Vertex (graph theory) #Graph algorithms #Planar graph #Graph #Undirected graph #Discrete mathematics
- A fast and simple randomized parallel algorithm for the maximal independent set problem
1986/12/01 by Noga Alon, László Babai, Alon Itai · 13 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constant (computer programming) #Deterministic algorithm #Discrete mathematics #Graph #Independent set #Limits and Structures in Graph Theory #Line graph #Mathematics #Maximal independent set #Pairwise comparison #Parallel algorithm #Pathwidth #Probabilistic analysis of algorithms #Probabilistic logic #Randomized algorithm #SIMPLE algorithm #Set (abstract data type) #Simple (philosophy)
- An Efficient Parallel Biconnectivity Algorithm
1985/11/01 by Robert E. Tarjan, Uzi Vishkin · 14 citations
Computer Science · Engineering · Mathematics · #Interconnection Networks and Systems #Parallel Computing and Optimization Techniques #Low-power high-performance VLSI design #Computer science #Parallel algorithm #Speedup #Parallel computing #Binary logarithm #Adjacency list #Adjacency matrix #Computation #Combinatorics #Graph #Algorithm #Undirected graph #Running time #Data structure #Mathematics #Theoretical computer science
- Fast Algorithms for Finding Nearest Common Ancestors
1984/05/01 by Dov Harel, Robert E. Tarjan, Robert Endre Tarjan · 55 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Artificial intelligence #Binary logarithm #Combinatorics #Computer science #DNA and Biological Computing #Data mining #Data structure #Discrete mathematics #Linear space #Mathematics #Measure (data warehouse) #Omega #Pointer (user interface) #Preprocessor #Time complexity #Upper and lower bounds #semigroups and automata theory
- Randomized speed-ups in parallel computation
1984/01/01 by Uzi Vishkin · 2 citations
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
- Comment: Algorithms for computing relative neighbourhood graph
1980/10/23 by Godfried T. Toussaint · 1 citation
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Optimization and Packing Problems #Neighbourhood (mathematics) #Algorithm #Graph #Binary logarithm #Graph algorithms #Computer science #Mathematics #Combinatorics #Discrete mathematics
- Finding a Minimum Circuit in a Graph
1978/11/01 by Alon Itai, Michael Rodeh · 17 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Combinatorics #Mathematics #Graph #Electronic circuit #Binary logarithm #Discrete mathematics #Graph theory #Minimum cut #Minimum weight #Algorithm
- Efficient Algorithms for Shortest Paths in Sparse Networks
1977/01/01 by D. Barton Johnson · 4 citations
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #Interconnection Networks and Systems #Complexity and Algorithms in Graphs #Combinatorics #Partition (number theory) #Algorithm #Binary logarithm #Integer (computer science) #Running time #Priority queue #Set (abstract data type) #Queue #Discrete mathematics #Computer science #Mathematics #Arc (geometry) #Class (philosophy)
- Finding Minimum Spanning Trees
1976/12/01 by David R. Cheriton, Robert E. Tarjan · 9 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Combinatorics #Spanning tree #Minimum spanning tree #Mathematics #Binary logarithm #Omega #Upper and lower bounds #k-minimum spanning tree #Discrete mathematics #Tree structure #Binary tree #K-ary tree #Physics
- Multidimensional binary search trees used for associative searching
1975/09/01 by Jon Louis Bentley, Jon Bentley · 375 citations
Computer Science · Mathematics · #Advanced Image and Video Retrieval Techniques #Algorithm #Algorithms and Data Compression #Arithmetic #Artificial intelligence #Binary logarithm #Binary number #Binary search algorithm #Binary search tree #Binary tree #Combinatorics #Computer science #Curse of dimensionality #Data Management and Algorithms #Data structure #Intersection (aeronautics) #Interval tree #Mathematics #Node (physics) #Optimal binary search tree #Range tree #Search algorithm #Search tree #Ternary search tree #Theoretical computer science #Tree (set theory) #Tree traversal #k-d tree
- A transitive closure algorithm
1970/03/01 by Paul W. Purdom, Paul Purdom · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Binary logarithm #Closure (psychology) #Combinatorics #Complexity and Algorithms in Graphs #Dijkstra's algorithm #Directed graph #Discrete mathematics #Floyd–Warshall algorithm #Graph #Line graph #Mathematics #Shortest path problem #Time complexity #Transitive closure #Transitive reduction #Transitive relation #Undirected graph #Voltage graph
prev