Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
The Cost of Changing Edges for Diameter Computation and More
Sam Hiken, Yael Kirkpatrick, Jakob Nogler +1
The sensitivity setting is a restricted setting for dynamic algorithms, particularly practical for scenarios where extensive preprocessing is feasible but responses to real-time mo…
cs.DS2024
Improved Hardness-of-Approximation for Token Swapping
Sam Hiken, Nicole Wein
We study the token swapping problem, in which we are given a graph with an initial assignment of one distinct token to each vertex, and a final desired assignment (again with one t…