Cover Image

Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Elkin, Michael, Trehan, Chhaya
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms F.0, F.2 F.0; F.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Paging with Heterogeneous Cache Slots
by: Chrobak, Marek, et al.
Published: (2022)

Calculation of the Comparative Efficiency of Algorithms Using a Single Metric
by: Chakraborty, Arya
Published: (2024)

Arcee: An OCM-Solver
by: Boehmer, Kimon, et al.
Published: (2024)

On the I/O Complexity of the CYK Algorithm and of a Family of Related DP Algorithms
by: De Stefani, Lorenzo, et al.
Published: (2024)

Clustering Permutations: New Techniques with Streaming Applications
by: Chakraborty, Diptarka, et al.
Published: (2022)

Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
by: Hušek, Radek, et al.
Published: (2020)

Deterministic Longest Common Subsequence Approximation in Near-Linear Time
by: Boneh, Itai, et al.
Published: (2025)

Planar Multiway Cut with Terminals on Few Faces
by: Pandey, Sukanya, et al.
Published: (2025)

The Pareto Frontier of Randomized Learning-Augmented Online Bidding
by: Degryse, Mathis, et al.
Published: (2026)

Faster Multi-Source Reachability and Approximate Distances via Shortcuts, Hopsets and Matrix Multiplication
by: Elkin, Michael, et al.
Published: (2025)

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

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

Efficient Approximation of Fractional Hypertree Width
by: Korchemna, Viktoriia, et al.
Published: (2024)

On the formalization of the notion of a concurrent algorithm
by: Middelburg, C. A.
Published: (2024)

Formalizing the notions of non-interactive and interactive algorithms
by: Middelburg, C. A.
Published: (2024)

Multiplication of 0-1 matrices via clustering
by: Jansson, Jesper, et al.
Published: (2025)

An Optimal Randomized Algorithm for Finding the Saddlepoint
by: Dallant, Justin, et al.
Published: (2024)

Which $L_p$ norm is the fairest? Approximations for fair facility location across all "$p$"
by: Gupta, Swati, et al.
Published: (2022)

Provably Small Portfolios for Multiobjective Optimization with Application to Subsidized Facility Location
by: Gupta, Swati, et al.
Published: (2025)

Deterministically Simulating Barely Random Algorithms in the Random-Order Arrival Model
by: Borodin, Allan, et al.
Published: (2025)

Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees
by: Gupta, Swati, et al.
Published: (2023)

Stochastic Function Certification with Correlations
by: Ghuge, Rohan, et al.
Published: (2026)

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
by: Chuzhoy, Julia, et al.
Published: (2025)

Approximation Algorithms for Capacitated Vehicle Routing Problems: A Comprehensive Survey
by: Chen, Yongyu
Published: (2023)

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

On the formalization of the notion of an algorithm
by: Middelburg, C. A.
Published: (2024)

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

Replicability in High Dimensional Statistics
by: Hopkins, Max, et al.
Published: (2024)

The Degree of Fairness in Efficient House Allocation
by: Hosseini, Hadi, et al.
Published: (2024)

New Entropy Measures for Tries with Applications to the XBWT
by: Carfagna, Lorenzo, et al.
Published: (2025)

Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
by: Chauhan, Archit, et al.
Published: (2026)

Max-Cut with $ε$-Accurate Predictions
by: Cohen-Addad, Vincent, et al.
Published: (2024)

PAC Learning is just Bipartite Matching (Sort of)
by: Dughmi, Shaddin
Published: (2025)

Engineering Compressed Matrix Multiplication with the Fast Walsh-Hadamard Transform
by: Andersson, Joel, et al.
Published: (2026)

Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique
by: Lingas, Andrzej
Published: (2024)

Min cost flow on unit capacity networks and convex cost K-flow are as easy as the assignment problem with All-Min-Cuts algorithm
by: Hochbaum, Dorit S.
Published: (2016)

Fast approximate $\ell$-center clustering in high dimensional spaces
by: Kowaluk, Mirosław, et al.
Published: (2025)

Faster Mixing for Triangulations via Transport Flows
by: Alev, Vedat Levi, et al.
Published: (2026)

Min-CSPs on Complete Instances
by: Anand, Aditya, et al.
Published: (2024)

Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs
by: Künnemann, Marvin, et al.
Published: (2024)