OOIR: Observatory of International Research

Papers

(The median citation count of ACM Transactions on Algorithms is 1. The table below lists those papers that are above that threshold based on CrossRef citation counts [max. 250 papers]. The publications cover those that have been published in the past four years, i.e., from 2020-03-01 to 2024-03-01.)

Article	Citations
Optimal-Time Dictionary-Compressed Indexes	23
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)	20
The Non-Uniform k -Center Problem	13
Linear-time String Indexing and Analysis in Small Space	13
Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs	11
Randomized Contractions Meet Lean Decompositions	11
Deterministic APSP, Orthogonal Vectors, and More	10
A Linear-Time Algorithm for Seeds Computation	10
Ramsey Spanning Trees and Their Applications	8
A Learned Approach to Design Compressed Rank/Select Data Structures	8
Time- and Space-optimal Algorithm for the Many-visits TSP	8
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time	8
An Improved Isomorphism Test for Bounded-tree-width Graphs	8
Zeros of Holant Problems	8
Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants	7
The Complexity of Cake Cutting with Unequal Shares	7
Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems	6
Doubly Balanced Connected Graph Partitioning	6
k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms	6
Holant Clones and the Approximability of Conservative Holant Problems	6
Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space	6
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry	6
Symmetry Exploitation for Online Machine Covering with Bounded Migration	6
A PTAS for Capacitated Vehicle Routing on Trees	6
Dynamic Parameterized Problems and Algorithms	5

Fine-grained Complexity Analysis of Two Classic TSP Variants	5
Parameterized Hardness of Art Gallery Problems	5
Deterministic Sparse Suffix Sorting in the Restore Model	5
SETH-based Lower Bounds for Subset Sum and Bicriteria Path	5
Improved Dynamic Graph Coloring	5
Querying a Matrix through Matrix-Vector Products	5
On the Complexity of String Matching for Graphs	4
Random Walks on Small World Networks	4
The Quest for Strong Inapproximability Results with Perfect Completeness	4
Tight Bounds for Online TSP on the Line	4
Edge Estimation with Independent Set Oracles	4
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem	4
Discrete Fréchet Distance under Translation	4
Fast and Perfect Sampling of Subgraphs and Polymer Systems	3
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems	3
A PTAS for Euclidean TSP with Hyperplane Neighborhoods	3
Testing Bounded Arboricity	3
Oblivious Resampling Oracles and Parallel Algorithms for the Lopsided Lovász Local Lemma	3
Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces	3
Zip Trees	3
Approximating Geometric Knapsack via L-packings	3
k -center Clustering under Perturbation Resilience	3
A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games	2
Constant-time Dynamic (Δ +1)-Coloring	2
Sparse Backbone and Optimal Distributed SINR Algorithms	2
Sublinear Random Access Generators for Preferential Attachment Graphs	2
Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems	2
Improving the Smoothed Complexity of FLIP for Max Cut Problems	2
A Simple Algorithm for Optimal Search Trees with Two-way Comparisons	2
Approximate Counting of k -Paths: Simpler, Deterministic, and in Polynomial Space	2
Online Service with Delay	2
Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm	2
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams	2
Maximum Matching in the Online Batch-arrival Model	2
Parameterized Approximation Algorithms for Bidirected Steiner Network Problems	2
Optimal Substring Equality Queries with Applications to Sparse Text Indexing	2
Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems	2
The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain	2
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching	2
2-Approximating Feedback Vertex Set in Tournaments	2
Hypergraph Isomorphism for Groups with Restricted Composition Factors	2
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter	2
Navigating in Trees with Permanently Noisy Advice	2
Exact Distance Oracles for Planar Graphs with Failing Vertices	2
Online Metric Algorithms with Untrusted Predictions	1
A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics	1
Finding a Shortest Odd Hole	1
A Colored Path Problem and Its Applications	1
Detecting Feedback Vertex Sets of Size k in O ^⋆ (2.7 k ) Time	1
On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?	1

On β-Plurality Points in Spatial Voting Games	1
Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams	1
Fully Dynamic (Δ +1)-Coloring in O (1) Update Time	1
4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n ^4/3	1
Fully Dynamic MIS in Uniformly Sparse Graphs	1
Structure Learning of H-Colorings	1
Submatrix Maximum Queries in Monge and Partial Monge Matrices Are Equivalent to Predecessor Search	1
Tight Bounds for ℓ ₁ Oblivious Subspace Embeddings	1
Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election	1
The Complexity of Approximately Counting Retractions to Square-free Graphs	1
Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs	1
Computing the Inverse Geodesic Length in Planar Graphs and Graphs of Bounded Treewidth	1
Approximating Pathwidth for Graphs of Small Treewidth	1
A Complexity Theoretical Study of Fuzzy K -Means	1
The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains	1
Algorithms for Weighted Independent Transversals and Strong Colouring	1
I/O-Efficient Algorithms for Topological Sort and Related Problems	1
Additive Sparsification of CSPs	1
Online Throughput Maximization on Unrelated Machines: Commitment is No Burden	1
On the External Validity of Average-case Analyses of Graph Algorithms	1
Online Algorithms for Weighted Paging with Predictions	1
Approximating Spanners and Directed Steiner Forest	1
Time Dependent Biased Random Walks	1
Rapid Mixing from Spectral Independence beyond the Boolean Domain	1
A Faster Algorithm for Finding Tarski Fixed Points	1
Point-Width and Max-CSPs	1
Universal Algorithms for Clustering Problems	1
Node-weighted Network Design in Planar and Minor-closed Families of Graphs	1
Popular Matchings with One-Sided Bias	1
Better Distance Preservers and Additive Spanners	1
Network Design for s - t Effective Resistance	1
PTAS for Sparse General-valued CSPs	1
Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension	1
Smaller Cuts, Higher Lower Bounds	1