Interval Separators in Temporal Graphs
摘要
This paper addresses the problem of identifying time interval separators in temporal networks. We introduce d-MinIntSep, a new variant of the temporal separator problem, which models failures as time intervals assigned to vertices and aims to block all temporal paths between a source and a target that can be completed within a given deadline d. We prove that the d-MinIntSep problem is NP-hard, and we propose an Integer Linear Programming (ILP) formulation to compute minimum interval separators. This latter method is evaluated on synthetic temporal networks derived from real-world transportation datasets. The experiments show that the method runtime is highly sensitive to temporal dimension and path density.