Optimal path discovery problem with homogeneous knowledge

DOI10.1007/S00224-019-09928-WMaRDI QIDQ2300623zbMATH OpenOpenAlexWikidataFDO

Authors Christopher Thraves Caro, Josu Doncel, Olivier Brun

Publication date 27 February 2020

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-019-09928-w

zbMATH Keywords

lower boundsoptimal pathquery ratioshortest path discovery problemupper bounds

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Economical graph discovery
• Shortest paths without a map
• Discovery of network properties with all-shortest-paths queries
• Computing shortest paths with uncertainty
• Discovery of Network Properties with All-Shortest-Paths Queries

Cites work

• A bidirectional shortest-path algorithm with good average-case behavior
• A note on two problems in connexion with graphs
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• An exact algorithm for the robust shortest path problem with interval data
• Bidirectional Heuristic Search Again
• Bidirectional heuristic search with limited resources
• Computing minimum spanning trees with uncertainty
• Computing shortest paths with uncertainty
• Computing the Median with Uncertainty
• Economical graph discovery
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Efficient update strategies for geometric computing with uncertainty
• Network flows. Theory, algorithms, and applications.
• On a routing problem
• On the complexity of the robust spanning tree problem with interval data
• Optimally solving permutation sorting problems with efficient partial expansion bidirectional heuristic search
• Query-competitive algorithms for cheapest set problems under uncertainty
• Shortest paths algorithms: Theory and experimental evaluation
• The robust spanning tree problem with interval data

Cited in

(4)

• Economical graph discovery
• Discovery of Network Properties with All-Shortest-Paths Queries
• Greediness is not always a vice: efficient discovery algorithms for assignment problems
• Discovery of network properties with all-shortest-paths queries

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Optimal path discovery problem with homogeneous knowledge

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