Cover Image

A Sublinear Algorithm for Approximate Shortest Paths in Large Networks

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Basu, Sabyasachi, Kōshima, Nadia, Eden, Talya, Ben-Eliezer, Omri, Seshadhri, C.
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Discrete Mathematics Social and Information Networks
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Spectral Triadic Decompositions of Real-World Networks
by: Basu, Sabyasachi, et al.
Published: (2022)

A note on approximating the average degree of bounded arboricity graphs
by: Eden, Talya, et al.
Published: (2026)

Aggregating maximal cliques in real-world graphs
by: Alon, Noga, et al.
Published: (2025)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2022)

Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
by: Paul-Pena, Daniel, et al.
Published: (2025)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2024)

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

Detecting Disjoint Shortest Paths in Linear Time and More
by: Akmal, Shyan, et al.
Published: (2024)

Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing
by: Chakrabarty, Deeparnab, et al.
Published: (2024)

Computing Approximate Pareto Frontiers for Submodular Utility and Cost Tradeoffs
by: Vombatkere, Karan, et al.
Published: (2026)

On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2023)

Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time
by: Li, Xiaxin, et al.
Published: (2025)

Staying Fresh: Efficient Algorithms for Timely Social Information Distribution
by: Li, Songhua, et al.
Published: (2023)

Tightest Admissible Shortest Path
by: Weiss, Eyal, et al.
Published: (2023)

Temporal Triadic Closure: Finding Dense Structures in Social Networks That Evolve
by: Davot, Tom, et al.
Published: (2024)

Approximation Algorithms for Optimal Hopsets
by: Dinitz, Michael, et al.
Published: (2025)

An Approximation Algorithm for Monotone Submodular Cost Allocation
by: Mizutani, Ryuhei
Published: (2025)

Additive Sparsification of CSPs
by: Pelleg, Eden, et al.
Published: (2021)

Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized Methods
by: Huang, Yufan, et al.
Published: (2023)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, et al.
Published: (2024)

Approximation Algorithms for the $b$-Matching and List-Restricted Variants of MaxQAP
by: Nanta, Jiratchaphat, et al.
Published: (2025)

A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
by: Liang, Wei, et al.
Published: (2024)

A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
by: Weiss, Eyal, et al.
Published: (2022)

Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network
by: Manna, Bubai, et al.
Published: (2024)

Greedy Algorithms for Shortcut Sets and Hopsets
by: Bals, Ben, et al.
Published: (2025)

Stable Approximation Algorithms for Dominating Set and Independent Set
by: de Berg, Mark, et al.
Published: (2024)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
by: Iwata, Satoru, et al.
Published: (2024)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
by: Bourneuf, Romain, et al.
Published: (2025)

Parameterized Complexity of Path Set Packing
by: Aravind, N. R., et al.
Published: (2022)

Path Contraction Faster than $2^n$
by: Agrawal, Akanksha, et al.
Published: (2025)

Approximating Submodular Matroid-Constrained Partitioning
by: Bérczi, Kristóf, et al.
Published: (2025)

An Approximate Generalization of the Okamura-Seymour Theorem
by: Kumar, Nikhil
Published: (2022)

Approximate Realizations for Outerplanaric Degree Sequences
by: Bar-Noy, Amotz, et al.
Published: (2024)

Tight Paths and Tight Pairs in Weighted Directed Graphs
by: Balcázar, José Luis
Published: (2025)

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
by: Fomin, Fedor V., et al.
Published: (2024)

A Constant-Factor Approximation for Directed Latency
by: Blauth, Jannis, et al.
Published: (2025)

Efficient Online Sensitivity Analysis For The Injective Bottleneck Path Problem
by: Kaymakov, Kirill V., et al.
Published: (2024)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Approximation algorithms for non-sequential star packing problems
by: Hu, Mengyuan, et al.
Published: (2024)

Approximation of Spanning Tree Congestion using Hereditary Bisection
by: Kolman, Petr
Published: (2024)