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 2021-05-01 to 2025-05-01.)

Article	Citations
A PTAS for Capacitated Vehicle Routing on Trees	21
A Face Cover Perspective to ℓ ₁ Embeddings of Planar Graphs	15
Collapsing the Tower—On the Complexity of Multistage Stochastic IPs	12
Cluster Editing Parameterized above Modification-disjoint P ₃ -packings	11
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems	9
Generic Techniques for Building Top- k Structures	9
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter	8
4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n ^4/3	8
Tiling with Squares and Packing Dominos in Polynomial Time	7
Minimum+1 ( s, t )-cuts and Dual-edge Sensitivity Oracle	6
On β-Plurality Points in Spatial Voting Games	5
Better Sum Estimation via Weighted Sampling	5
Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs	5
Online Euclidean Spanners	5
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry	5
Perfect Resolution of Strong Conflict-Free Colouring of Interval Hypergraphs	5
Competitive Online Search Trees on Trees	4
Dynamic Geometric Set Cover and Hitting Set	4
Online Lewis Weight Sampling	4
The Query Complexity of Searching Trees with Permanently Noisy Advice	4
The Infinite Server Problem	4
Introduction: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2022 Special Issue	4
On the Complexity of Symmetric vs. Functional PCSPs	4
Combinatorial Generation via Permutation Languages. IV. Elimination Trees	4
Computing the Inverse Geodesic Length in Planar Graphs and Graphs of Bounded Treewidth	3

Faster Matroid Partition Algorithms	3
Introduction to the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019 Special Issue	3
A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence	3
Counting Homomorphic Cycles in Degenerate Graphs	3
SETH-based Lower Bounds for Subset Sum and Bicriteria Path	3
Network Design for s - t Effective Resistance	3
Hypergraph Isomorphism for Groups with Restricted Composition Factors	3
Quantum Speed-Ups for String Synchronizing Sets, Longest Common Substring, and k -mismatch Matching	3
Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling	3
On the Complexity of String Matching for Graphs	3
A Simple Algorithm for Optimal Search Trees with Two-way Comparisons	3
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree	3
Hopcroft’s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision Trees	3
A Cubic Algorithm for Computing the Hermite Normal Form of a Nonsingular Integer Matrix	3
Map Matching Queries on Realistic Input Graphs Under the Fréchet Distance	3
A Lower Bound on Cycle-Finding in Sparse Digraphs	3
Improving the Smoothed Complexity of FLIP for Max Cut Problems	3
Smaller Cuts, Higher Lower Bounds	3
String Indexing with Compressed Patterns	2
Rerouting Planar Curves and Disjoint Paths	2
Introduction to the Special Issue on ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020	2
Efficiency of Self-Adjusting Heaps	2
Approximate Counting of k -Paths: Simpler, Deterministic, and in Polynomial Space	2
Time Dependent Biased Random Walks	2
New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages	2
The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication	2
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems	2
Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension	2
Online Throughput Maximization on Unrelated Machines: Commitment is No Burden	2
Competitive Data-Structure Dynamization	2
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams	2
On Two-Handed Planar Assembly Partitioning with Connectivity Constraints	2
A Faster Algorithm for Finding Tarski Fixed Points	2
Online Service with Delay	2
Exact Distance Oracles for Planar Graphs with Failing Vertices	2
True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs	2
Classification via Two-Way Comparisons	1
Tiny Pointers	1
Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead	1
Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity Bounds	1
Isomorphism Testing for Graphs Excluding Small Topological Subgraphs	1
Scalable High-Quality Hypergraph Partitioning	1
Detecting Feedback Vertex Sets of Size k in O ^⋆ (2.7 k ) Time	1
Deterministic Replacement Path Covering	1
Approximating Sparsest Cut in Low-treewidth Graphs via Combinatorial Diameter	1
Constant-time Dynamic (Δ +1)-Coloring	1
On the Two-Dimensional Knapsack Problem for Convex Polygons	1
Static and Streaming Data Structures for Fréchet Distance Queries	1
Approximating Pathwidth for Graphs of Small Treewidth	1
Automorphisms and Isomorphisms of Maps in Linear Time	1

Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable	1
Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs	1
Editorial	1
Popular Arborescences and Their Matroid Generalization	1
Tight Bounds for ℓ ₁ Oblivious Subspace Embeddings	1
Polynomial-time trace reconstruction in the smoothed complexity model	1
Exponential Separations in Local Privacy	1
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs	1
Discrete Fréchet Distance under Translation	1
PTAS for Sparse General-valued CSPs	1
Popular Matchings with One-Sided Bias	1
Optimal Inapproximability with Universal Factor Graphs	1
Strict Fibonacci Heaps	1
Computing MEMs and Relatives on Repetitive Text Collections	1