Cover Image

Single-Source Regular Path Querying in Terms of Linear Algebra

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Belyanin, Georgiy, Grigoriev, Semyon, Suvorov, Rodion
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Evaluating Regular Path Queries on Compressed Adjacency Matrices
by: Arroyuelo, Diego, et al.
Published: (2023)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
by: Fischer, Nick, et al.
Published: (2024)

Numerical Linear Algebra in Linear Space
by: Liu, Yiping, et al.
Published: (2025)

Undirected Replacement Paths: Dual Fault Reduces to Single Source
by: Nogler, Jakob, et al.
Published: (2026)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
by: Bernstein, Aaron, et al.
Published: (2022)

On Differentially Private Linear Algebra
by: Kaplan, Haim, et al.
Published: (2024)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
by: Atalig, Sunny, et al.
Published: (2024)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
by: Yan, Shuyi
Published: (2025)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
by: Khanna, Sanjeev, et al.
Published: (2026)

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
by: Harada, Kaito, et al.
Published: (2024)

Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm for Single-Source Shortest Paths
by: Castro, Lucas, et al.
Published: (2025)

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths
by: Atalig, Sunny, et al.
Published: (2025)

Verifying Shortest Paths in Linear Time
by: Shokry, Ahmed, et al.
Published: (2024)

Incremental Approximate Single-Source Shortest Paths with Predictions
by: McCauley, Samuel, et al.
Published: (2025)

Faster Linear-Space Data Structures for Path Frequency Queries
by: Rata, Ovidiu
Published: (2026)

Faster Linear-Size And-Or Path and Adder Circuits
by: Brenner, Ulrich, et al.
Published: (2024)

Path-Reporting Distance Oracles with Linear Size
by: Neiman, Ofer, et al.
Published: (2024)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
by: Haeupler, Bernhard, et al.
Published: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Single-Source Shortest Path Problem in Weighted Disk Graphs
by: An, Shinwoo, et al.
Published: (2025)

Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth
by: Liu, Yuxi, et al.
Published: (2026)

Notes on the Linear Algebraic View of Regularity Lemmas
by: Bodwin, Greg, et al.
Published: (2025)

A Faster Directed Single-Source Shortest Path Algorithm
by: Duan, Ran, et al.
Published: (2026)

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
by: Duan, Ran, et al.
Published: (2025)

Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
by: Terao, Tatsuya
Published: (2024)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
by: Bucić, Matija, et al.
Published: (2025)

Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method
by: Liu, Yang P.
Published: (2025)

Approximating Single-Source Personalized PageRank with Absolute Error Guarantees
by: Wei, Zhewei, et al.
Published: (2024)

Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
by: Wang, Samson, et al.
Published: (2023)

Fine-Grained Complexity of Regular Path Queries
by: Casel, Katrin, et al.
Published: (2021)

Adaptive BSTs for Single-Source and All-to-All Requests: Algorithms and Lower Bounds
by: Shiran, Maryam
Published: (2025)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
by: Bishnu, Arijit, et al.
Published: (2025)

Query-decision Regression between Shortest Path and Minimum Steiner Tree
by: Tong, Guangmo, et al.
Published: (2024)

Parameterized Complexity of MinCSP over the Point Algebra
by: Osipov, George, et al.
Published: (2023)

Optimizing Periodic Operations for Efficient Inland Waterway Lock Management
by: Golak, Julian, et al.
Published: (2025)

A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs
by: Grigoriev, Alexander, et al.
Published: (2025)

Submodular Maximization in Exactly $n$ Queries
by: Balkanski, Eric, et al.
Published: (2024)

First Passage Percolation with Queried Hints
by: Karntikoon, Kritkorn, et al.
Published: (2024)

Learning Partitions using Rank Queries
by: Chakrabarty, Deeparnab, et al.
Published: (2024)