Exploration of k-edge-deficient temporal graphs
Exploration of k-edge-deficient temporal graphs
复制标题
k 边缺陷时间图的探索
DOI：
10.1007/s00236-022-00421-5
复制
发表时间：
2022
期刊：
影响因子：
0.6
通讯作者：
Erlebach T
中科院分区：
文献类型：
--
作者：
Erlebach T
一个具有生命周期的时间图是一个称为层的图的序列，所有这些图都有相同的顶点集，但可以有不同的边集。底层图是顶点为setv的图，它包含至少在一个层中出现的所有边。如果每一层都是连通图，则时间图总是连通的；如果每一层都包含底层图的除大多数边缘外的所有边缘，则时间图是风险缺边的。对于给定的起始点，时间探索是一种时间漫步，它从顶点开始，至多遍历每层中的一条边，并访问时间图的所有顶点。我们证明了具有足够生命周期的总是连通的k边缺陷时间图总是可以在时间步长中被探索。我们还构造了总是连通的，缺少k边的时间图，其中任何探索都需要时间步长。对于总是连通的，缺少1条边的时间图，我们证明了ato (n)个时间步足以进行时间探索。
A temporal graph with lifetimeLis a sequence ofLgraphs, called layers, all of which have the same vertex setVbut can have different edge sets. The underlying graph is the graph with vertex setVthat contains all the edges that appear in at least one layer. The temporal graph is always connected if each layer is a connected graph, and it isk-edge-deficient if each layer contains all except at mostkedges of the underlying graph. For a given start vertexs, a temporal exploration is a temporal walk that starts ats, traverses at most one edge in each layer, and visits all vertices of the temporal graph. We show that always-connected,k-edge-deficient temporal graphs with sufficient lifetime can always be explored intime steps. We also construct always-connected,k-edge-deficient temporal graphs for which any exploration requirestime steps. For always-connected, 1-edge-deficient temporal graphs, we show thatO(n) time steps suffice for temporal exploration.
登录
查看更多内容
DOI：
--
发表时间：
2018
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
T. Erlebach;Jakob T. Spooner
通讯作者：
Jakob T. Spooner
影响因子：
0.5
作者：
D. Ilcinkas;A. Wade
通讯作者：
A. Wade
DOI：
--
发表时间：
2022
期刊：
Publicationes mathematicae (Debrecen)
影响因子：
--
作者：
F. Harary;G. Prins
通讯作者：
G. Prins
基于Cactuses的常连通动态图探索
DOI：
--
发表时间：
2014
期刊：
Colloquium on Structural Information & Communication Complexity
影响因子：
--
作者：
D. Ilcinkas;R. Klasing;A. Wade
通讯作者：
A. Wade
关于探索小路径宽度的始终连接的时间图
影响因子：
0.5
作者：
H. Bodlaender;Tom C. van der Zanden
通讯作者：
Tom C. van der Zanden