- Negative-Weight Single-Source Shortest Paths in Near-linear Time
2022/03/07 by Aaron Bernstein, Bernstein, Aaron, Danupon Nanongkai +4 · 2 voices · 21 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Binary logarithm #Combinatorial algorithms #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete mathematics #Graph #Mathematics #Planar graph #Randomized algorithm #Running time #Simple (philosophy) #Tilde #Time complexity
- An Optimal Separation of Randomized and Quantum Query Complexity
2020/08/24 by Alexander A. Sherstov, Sherstov, Alexander A., Andrey A. Storozhenko +3 · 4 citations
Computer Science · Mathematics · #Binary logarithm #Boolean function #Bounded function #Combinatorics #Communication complexity #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computer science #Conjecture #Constant (computer programming) #Discrete mathematics #FOS: Computer and information sciences #FOS: Physical sciences #Integer (computer science) #Mathematical analysis #Mathematics #Omega #Order (exchange) #Physics #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum mechanics #Randomized algorithm #Stochastic Gradient Optimization Techniques #Tree (set theory) #Upper and lower bounds
- Zip Trees
2018/06/18 by Robert E. Tarjan, Caleb C. Levy, Caleb Levy +1 · 2 voices · 4 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Arithmetic #Artificial intelligence #Binary logarithm #Binary number #Binary search tree #Binary tree #Combinatorics #Computer science #Discrete mathematics #Genomics and Phylogenetic Studies #Heap (data structure) #Interval tree #K-ary tree #Machine Learning and Algorithms #Mathematics #Node (physics) #Optimal binary search tree #Pointer (user interface) #Random binary tree #Range tree #Rank (graph theory) #Search algorithm #Search tree #Self-balancing binary search tree #Ternary search tree #Tree (set theory) #Tree structure #Weight-balanced tree #cs.DS
- Data Structures for Weighted Matching and Extensions to b-matching and\n f-factors
2016/11/22 by Harold N. Gabow, Gabow, Harold N. · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Binary logarithm #Bipartite graph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Data Structures and Algorithms (cs.DS) #Degree (music) #Discrete mathematics #FOS: Computer and information sciences #Graph #Matching (statistics) #Mathematics #Optimization and Search Problems #Path (computing) #Physics #Shortest path problem #Statistics #Time complexity #Tree (set theory) #Upper and lower bounds #cs.DS
- A Lower Bound for the Distributed Lovász Local Lemma
2015/11/03 by Sebastian Brandt, Brandt, Sebastian, Orr Fischer +13 · 14 citations
Computer Science · Mathematics · #Binary logarithm #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Degree (music) #Discrete mathematics #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Graph #Lemma (botany) #Mathematics #Monte Carlo method #Omega #Optimization and Search Problems #Parallel #Statistics #Upper and lower bounds #and Cluster Computing (cs.DC) #cs.CC #cs.DC
- Faster deterministic Feedback Vertex Set
2013/06/15 by Tomasz Kociumaka, Marcin Pilipczuk, Kociumaka, Tomasz +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Binary logarithm #Branching (polymer chemistry) #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Feedback vertex set #Graph #Mathematics #Parameterized complexity #Reduction (mathematics) #Running time #Set (abstract data type) #Simple (philosophy) #Vertex (graph theory) #cs.DS
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
2012/06/08 by Holger Dell, Thore Husfeldt, Dániel Marx +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Binary logarithm #Chromatic polynomial #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Enumeration #Exponential function #Exponential time hypothesis #Graph #Lemma (botany) #Markov Chains and Monte Carlo Methods #Mathematics #Multigraph #Satisfiability #Time complexity #Tutte polynomial #Vertex (graph theory) #cs.CC #cs.DS #math.CO
- A Faster Grammar-Based Self-Index
2011/09/19 by Travis Gagie, Paweł Gawrychowski, Gagie, Travis +7 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Artificial intelligence #Binary logarithm #Combinatorics #Computer science #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #Geometry #Grammar #Index (typography) #Line (geometry) #Mathematics #Natural Language Processing Techniques #Parsing #Programming language #Rule-based machine translation #Space (punctuation) #String (physics) #cs.DS
- An improved construction of progression-free sets
2011/07/30 by Michael Elkin · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Binary logarithm #Combinatorics #Discrete mathematics #Limits and Structures in Graph Theory #Mathematical analysis #Mathematics #Omega #Physics #Quantum mechanics #Upper and lower bounds
- Finding, minimizing, and counting weighted subgraphs
2009/05/31 by Virginia Vassilevska, Ryan Williams · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Interconnection Networks and Systems #Combinatorics #Time complexity #Mathematics #Exponent #Discrete mathematics #Matrix multiplication #Graph #Node (physics) #Binary logarithm
- Approximating rank-width and clique-width quickly
2008/11/01 by Sang‐il Oum · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #Matroid #Combinatorics #Mathematics #Running time #Rank (graph theory) #Submodular set function #Discrete mathematics #Extension (predicate logic) #Graph #Function (biology) #Binary logarithm #Algorithm #Computer science
- Approximate distance oracles
2005/01/01 by Mikkel Thorup, Uri Zwick · 84 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Conjecture #Data structure #Discrete mathematics #Edit distance #Girth (graph theory) #Graph #Graph Labeling and Dimension Problems #Integer (computer science) #Mathematics #Oracle #Quotient #Simple (philosophy) #Space (punctuation)
- 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 · 2 citations
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
- Balanced graph partitioning
2004/06/27 by Konstantin Andreev, Harald Räcke · 1 citation
Computer Science · Engineering · Mathematics · #Approximation algorithm #Binary logarithm #Combinatorics #Computer science #Constant (computer programming) #Discrete mathematics #Generalization #Graph #Graph partition #Interconnection Networks and Systems #Low-power high-performance VLSI design #Mathematics #Time complexity #VLSI and FPGA Design Techniques
- Finding the Sink Takes Some Time: An Almost Quadratic Lower Bound for Finding the Sink of Unique Sink Oriented Cubes
2004/03/01 by Tibor Szab�, Ingo Schurr · 1 citation
Computer Science · Mathematics · #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Data Management and Algorithms #Discrete mathematics #Geometry #Mathematics #Oracle #Quadratic equation #Simplex #Sink (geography) #Time complexity #Upper and lower bounds #Vertex (graph theory)
- Efficient Algorithms for the Hamiltonian Problem on Distance-Hereditary Graphs
2002/01/01 by Sun-yuan Hsieh, Sun‐Yuan Hsieh, Chin-Wen Ho +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Hamiltonian path #Mathematics #Optimization and Search Problems #Parallel algorithm #Running time #Time complexity #Tree (set theory)
- A General Approximation Technique for Constrained Forest Problems
1995/04/01 by Michel X. Goemans, David P. Williamson · 4 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems #Travelling salesman problem #Steiner tree problem #Approximation algorithm #Mathematics #Combinatorics #Triangle inequality #Shortest path problem #Matching (statistics) #Time complexity #Connection (principal bundle) #Binary logarithm #Covering problems #Discrete mathematics #Mathematical optimization #Graph #Computer science
- A Faster Deterministic Maximum Flow Algorithm
1994/11/01 by Valerie King, V. King, S. Rao +3 · 5 citations
Computer Science · Economics, Econometrics and Finance · Mathematics · #Advanced Graph Theory Research #Algorithm #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computation #Computer science #Constant (computer programming) #Control flow graph #Deterministic algorithm #Dijkstra's algorithm #Directed graph #Discrete mathematics #Flow (mathematics) #Freivalds' algorithm #Game Theory and Voting Systems #Graph #Mathematics #Maximum flow problem #Randomized algorithm #Running time #Shortest path problem #Time complexity
- Recursive Star-Tree Parallel Data Structure
1993/04/01 by Omer Berkman, Uzi Vishkin · 4 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · #Algorithms and Data Compression #Network Packet Processing and Optimization #DNA and Biological Computing #Ackermann function #Recursion (computer science) #Parallel algorithm #Star (game theory) #Generalization #Computer science #Tree (set theory) #Inverse #Binary logarithm #Data structure #Function (biology) #Combinatorics #Computation #Binary tree #Discrete mathematics #Algorithm #Mathematics
- RANDOMIZED PARALLEL ALGORITHMS FOR TRAPEZOIDAL DIAGRAMS
1992/06/01 by Kenneth L. Clarkson, Richard Cole, Robert E. Tarjan · 2 citations
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
- Locality in Distributed Graph Algorithms
1992/02/01 by Nathan Linial · 117 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Distributed algorithm #Distributed computing #Graph #Locality #Mathematics #Omega #Optimization and Search Problems #Time complexity #Upper and lower bounds #Vertex (graph theory)
- Simple Constructions of Almost k‐wise Independent Random Variables
1992/01/01 by Noga Alon, Oded Goldreich, Johan Håstad +1 · 2 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Limits and Structures in Graph Theory #Mathematics #Simple (philosophy) #Combinatorics #Distribution (mathematics) #Discrete mathematics #Binary logarithm #Upper and lower bounds #Random variable #Log-log plot #Point (geometry) #Space (punctuation) #Statistics #Mathematical analysis #Computer science #Geometry
- On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
1991/06/01 by János Pach, Micha Sharir · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Digital Image Processing Techniques #Combinatorics #Line segment #Line (geometry) #Upper and lower bounds #Mathematics #Point (geometry) #Queue #Omega #Visibility #Binary logarithm #Algorithm #Geometry #Computer science #Physics #Mathematical analysis #Optics
- 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
- 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
more