Nondecreasing paths in a weighted graph or: how to optimally read a train schedule

DOI10.1145/1824777.1824790zbMATH Open1300.90061OpenAlexW1978868826MaRDI QIDQ2930352FDOQ2930352

Authors: Virginia Vassilevska Williams 

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1824777.1824790

Recommendations

• A simple approach to nondecreasing paths
• Near optimum paths in time-table graphs
• Exact train pathing
• Improved time bounds for all pairs non-decreasing paths in general digraphs
• Minimum weight paths in time-dependent networks

zbMATH Keywords

shortest pathsmatrix productssingle sourcenondecreasing pathsall pairsearliest arrivals

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cited In (5)

• Faster Algorithms for All Pairs Non-Decreasing Paths Problem
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• Improved time bounds for all pairs non-decreasing paths in general digraphs
• Paying less for train connections with MOTIS
• A simple approach to nondecreasing paths

This page was built for publication: Nondecreasing paths in a weighted graph or: how to optimally read a train schedule

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2930352)