论文标题
计数时间路径
Counting Temporal Paths
论文作者
论文摘要
顶点V的中间性是一个重要的集中度度量，它量化了其他顶点对之间的最佳路径访问v。计算时间表中的中心性，在时间图中，边缘集可能会在离散的时间段上改变，要求我们计算与某些标准相对于某些标准最佳的时间途径。对于几种自然的最优性概念，包括最初或最快的时间路径，此计数问题将减少到#Temporal路径，这是在固定的一对顶点之间计算所有时间路径的问题；就像计数的问题和最快的时间路径一样，#Temporal路径通常是＃P-HARD。在这个棘手问题的许多应用中，我们启动了对#Temsoal路径的定位和近似复杂性的系统研究。我们表明，问题可能不接受静态下图的反馈顶点数量的FPT-Algorithm，并且一般很难近似。从积极的一面来看，我们证明了特殊情况的几个精确而近似的FPT-Algorithm。
The betweenness centrality of a vertex v is an important centrality measure that quantifies how many optimal paths between pairs of other vertices visit v. Computing betweenness centrality in a temporal graph, in which the edge set may change over discrete timesteps, requires us to count temporal paths that are optimal with respect to some criterion. For several natural notions of optimality, including foremost or fastest temporal paths, this counting problem reduces to #Temporal Path, the problem of counting all temporal paths between a fixed pair of vertices; like the problems of counting foremost and fastest temporal paths, #Temporal Path is #P-hard in general. Motivated by the many applications of this intractable problem, we initiate a systematic study of the prameterised and approximation complexity of #Temporal Path. We show that the problem presumably does not admit an FPT-algorithm for the feedback vertex number of the static underlying graph, and that it is hard to approximate in general. On the positive side, we proved several exact and approximate FPT-algorithms for special cases.
