Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
David C. Kutner, Anouk Sommer
In train networks, carefully-chosen delays may be beneficial for certain passengers, who would otherwise miss some connection. Given a simple (directed or undirected) temporal grap…
cs.DS2025
Generalising the maximum independent set algorithm via Boolean networks
Maximilien Gadouleau, David C. Kutner
A simple greedy algorithm to find a maximal independent set (MIS) in a graph starts with the empty set and visits every vertex, adding it to the set if and only if none of its neig…