Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
Fast and Simple Sorting Using Partial Information
Bernhard Haeupler, Richard Hladík, John Iacono +3
We consider the problem of sorting items, given the outcomes of pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in $O(m + \log T…
cs.DS2023
Distances and shortest paths on graphs of bounded highway dimension: simple, fast, dynamic
Sébastien Collette, John Iacono
Dijkstra's algorithm is the standard method for computing shortest paths on arbitrary graphs. However, it is slow for large graphs, taking at least linear time. It has been long kn…