Temporal graph realization with bounded stretch ☆

Mertzios, George B.

Temporal graph realization with bounded stretch ☆

2026-05-01

0

PRE

AI

DOI：

原文求助

摘要

En 中文

周期性时序图的最简形式是一种图，其中每条边在前A个时间步中恰好出现一次，然后每隔A个时间步重复出现一次，其中A为给定的周期长度。从网络设计角度来看，一项关键任务是以某种方式优化某些标准来分配边的时间标签。本文引入了一个非常自然的优化标准，用于衡量所有顶点对之间的时序距离与它们在基础静态图中的距离相比的拉伸程度。给定一个静态图G，任务是给每条边分配一个介于1和A之间的时间标签，使得在周期为A的周期性时序图中，从任何顶点u到任何其他顶点v的最快时序路径的持续时间不超过u和v在G中距离的alpha倍。这里，alpha的值衡量了在分配周期性时间标签后允许最短路径拉伸的程度。我们的研究涵盖了三个不同方向：首先，我们提供了一系列近似和NP困难性结果。其次，我们提供近似和固定参数算法。其中，我们提供了一个简单的算法，保证近似值严格小于A。第三，我们考虑了一个参数化的局部搜索扩展问题，其中给定图的时间标签，但允许改变最多k条边的时间标签。(c) 2026 作者。由Elsevier公司出版。这是一篇开放获取文章，遵循CC BY许可（http://creativecommons.org/licenses/by/4.0/）。

Keyword:

Temporal graph

Periodic temporal labeling

Fastest temporal path

Graph realization

Temporal connectivity

Stretch

Temporal graph realization with bounded stretch ☆

摘要

期刊

机构

引用论文