Cover Image

Approximating the shortest path problem with scenarios

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kasperski, Adam, Zielinski, Pawel
Format:	Preprint
Published:	2018
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computational complexity of the recoverable robust shortest path problem in acyclic digraphs
by: Kasperski, Adam, et al.
Published: (2024)

Recoverable robust shortest path problem under interval budgeted uncertainty representations
by: Jackiewicz, Marcel, et al.
Published: (2024)

Solving the all pairs shortest path problem after minor update of a large dense graph
by: Liu, Gangli
Published: (2024)

Faster negative length shortest paths by bootstrapping hop reducers
by: Huang, Yufan, et al.
Published: (2025)

Are there graphs whose shortest path structure requires large edge weights?
by: Bernstein, Aaron, et al.
Published: (2023)

Forcing a unique minimum spanning tree and a unique shortest path
by: Gima, Tatsuya, et al.
Published: (2025)

Faster single-source shortest paths with negative real weights via proper hop distance
by: Huang, Yufan, et al.
Published: (2024)

Graph neural networks extrapolate out-of-distribution for shortest paths
by: Nerem, Robert R., et al.
Published: (2025)

Centrality of shortest paths: Algorithms and complexity results
by: Phosavanh, Johnson, et al.
Published: (2024)

A parallel algorithm for the odd two-face shortest k-disjoint path problem
by: Chakraborty, Srijan, et al.
Published: (2025)

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

Finding longer cycles via shortest colourful cycle
by: Björklund, Andreas, et al.
Published: (2024)

Better Indexing for Rectangular Pattern Matching
by: Gawrychowski, Paweł, et al.
Published: (2025)

On Incremental Approximate Shortest Paths in Directed Graphs
by: Górkiewicz, Adam, et al.
Published: (2025)

Approximating optimization problems in graphs with locational uncertainty
by: Bougeret, Marin, et al.
Published: (2022)

Faster shortest-path algorithms using the acyclic-connected tree
by: Stefansson, Elis, et al.
Published: (2025)

An efficient implementation for solving the all pairs minimax path problem in an undirected dense graph
by: Liu, Gangli
Published: (2024)

Balancing Two-Dimensional Straight-Line Programs
by: Boneh, Itai, et al.
Published: (2025)

Faster two-dimensional pattern matching with $k$ mismatches
by: Ellert, Jonas, et al.
Published: (2024)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Approximately covering vertices by order-$5$ or longer paths
by: Gong, Mingyang, et al.
Published: (2024)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
by: Bieliński, Paweł Rafał, et al.
Published: (2026)

Faster ED-String Matching with $k$ Mismatches
by: Gawrychowski, Paweł, et al.
Published: (2025)

Enumerating All Directed Spanning Trees in Optimal Time
by: Gawrychowski, Paweł, et al.
Published: (2026)

Optimal Distance Labeling for Permutation Graphs
by: Gawrychowski, Paweł, et al.
Published: (2024)

On Approximating Cutwidth and Pathwidth
by: Bansal, Nikhil, et al.
Published: (2023)

Approximating $δ$-Covering
by: Hartmann, Tim A., et al.
Published: (2024)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
by: Gawrychowski, Paweł, et al.
Published: (2024)

Dynamic Longest Common Substring in Polylogarithmic Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2020)

Enumerating m-Length Walks in Directed Graphs with Constant Delay
by: Adamson, Duncan, et al.
Published: (2024)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
by: Lokshtanov, Daniel, et al.
Published: (2026)

Equivalences between Non-trivial Variants of 3LDT and Conv3LDT
by: Dudek, Bartłomiej, et al.
Published: (2020)

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

The Impact of Approximation on Algorithmic Progress
by: Li, Jeffery, et al.
Published: (2026)

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

Girth Approximations in the CONGEST Model
by: Chechik, Shiri, et al.
Published: (2026)

Optimized 2-Approximation of Treewidth
by: Belbasi, Mahdi, et al.
Published: (2024)

Approximate counting of permutation patterns
by: Ben-Eliezer, Omri, et al.
Published: (2024)

Supermodular Approximation of Norms and Applications
by: Kesselheim, Thomas, et al.
Published: (2024)

Consistent Low-Rank Approximation
by: Woodruff, David P., et al.
Published: (2026)