Theory & Algorithms · Computer Science & AI
Data Structures & Algorithms
The newest papers in Data Structures & Algorithms that ReadSearch has read, newest first. Each links to its own page, with its authors, date, where it was published and the original.
1,174 papers, from 4 September 2026 to 5 November 2026: 1,174 arXiv preprints.
Get the few papers worth your time in Data Structures & Algorithms every morning.
Follow Data Structures & Algorithms and ReadSearch reads its new papers each day, then brings you the few worth reading, each with its key finding in a sentence.
Newest papers, page 24
Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time
In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two trends in fine-grained…Per-State Signatures and Mean Time-to-Failure: An Algorithm for Systems With Simultaneous Failures
We present an algorithm that computes the structural signature and the mean time-to-failure (MTTF) of a monotone binary system at every one of its states, rather than only at the state in which all…Geometric Graph Representations via Compact SAT Encodings
We present compact SAT encodings and certifying exact solvers for boxicity and cubicity.Tree Edit Distance: Near-Linear-Time Approximate, Sublinear, and Dynamic
Tree edit distance (TED), the analog of string edit distance (ED) for hierarchical data, is the minimum number of node insertions, deletions, and substitutions transforming one labeled rooted…Subgraph Counting with Local Node Differential Privacy
We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees in analyses of distributed…Near-Optimal Parallel $M$-Matrix Scaling
In this paper we consider the problem of computing a positive diagonal scaling of a $d \times d$ symmetric $M$-matrix so that all row and column sums are $1$.An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube
Acyclic Unique Sink Orientations (AUSOs) of the binary hypercube form an elegant abstraction of various optimization problems, ranging from linear programs whose feasibility region is a…Hard Instances on Demand
The conclusions of an experimental study of algorithms are only as good as the instances they are run on.Fast Distributed $(Δ+ 1)$-Edge Coloring in Bipartite Graphs
We show that, on bipartite $n$-vertex graphs in the LOCAL model of distributed computation, $(Δ+ 1)$-edge coloring can be solved deterministically in $O(f(Δ) \log n)$ rounds for some function $f$.Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach
We present a simple deterministic semi-streaming algorithm that computes a $(1-\varepsilon)$-approximate maximum matching in general graphs in $O(1/\varepsilon^{2})$ passes.Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
We study learning-augmented streaming algorithms for estimating the value of Boolean Maximum Constraint Satisfaction Problems (Max-CSPs).Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage
The Emergency Vertex Cover problem (Em-VC) assigns budgets to stations at graph vertices to cover every edge while minimizing the total budget.Revisiting Non-Adaptive Set Membership Schemes: Removing the Logarithmic Factor
We study non-adaptive bit-probe schemes for static set membership.Dynamic 3-Coloring of Bipartite Graphs with Optimal Locality
We give a dynamic graph algorithm which maintains a 3-coloring in bipartite graphs under edge insertions such that the coloring only changes within a radius of $O(\log n)$ around an inserted edge.Exact Cut Complexity of Equal-Length Proportional Cake Cutting
We study proportional cake cutting under an equal-length constraint, where each of $n$ agents must receive a bundle of length exactly $1/n$ that is worth at least $1/n$ to that agent.Output-linear time enumeration of potential maximal cliques
First defined by Bouchitté and Todinca, Potential Maximal Cliques (PMC) are a well studied notion in graph theory due to its numerous applications.Optimal Online Stochastic Matching
We resolve the problem of unweighted online stochastic matching with a known arrival law by establishing its optimal competitive ratio.Towards Dynamic Top-$k$ Simple Shortest Paths
Computing the top-$k$ \textit{simple} shortest paths between two vertices of a graph, i.e., solving the P-KSSP problem, is a fundamental primitive in graph analytics.Undirected Network Coding and Faster External-Memory Integer Sorting
Network coding allows intermediate nodes to combine messages.An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint
We give a randomized polynomial-time $0.48$-approximation for maximizing a nonnegative non-monotone $k$-submodular function under a matroid constraint, for every $k\ge2$.