Time and date: 20 March 2024 at 2:00 pm | Location: Abacws 1.04 | Speaker: Daniel Hambly
In this talk, we consider the NP-hard problem of finding fixed-length paths in edge-weighted graphs. That is, we want to find a path (a sequence of vertices and edges where they can appear in the path at most once) in a network from one point to another where the total length of the path, in terms of the sum of its edge weights, is as close to possible as some prescribed length k. A particular application of interest is that of exercise. A street network can be conceptualised as a graph, where intersections and dead ends act as vertices, and roads as edges. Designing a workout route for activities like walking, running, or cycling, involves determining a path from a starting point to a destination within a specified number of steps, calories to be burned, or distance to cover. The selection of criteria, such as steps, calories, or distance, would define the weights assigned to the edges, making the task akin to identifying a path of a fixed length. Routing services are a feasible option for finding a solution, although they usually focus on routes with minimum length (weight) rather than a specific length.
