3 papers
math.CO2024
Vertex Ranking of Degenerate Graphs
John Iacono, Piotr Micek, Pat Morin +1
An -vertex-ranking of a graph is a colouring of the vertices of with integer colours so that in any connected subgraph of with diameter at most , there…
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…