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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Interval Separators in Temporal Graphs

  • Riccardo Dondi,
  • Mehdi Hosseinzadeh

摘要

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.