Shortcut sets are a vital instrument for reducing the diameter of a static graph and, consequently, its shortest path complexity, which is relevant in numerous subfields of graph theory. We explore the notion of shortcut sets in temporal graphs, which incorporate a discrete time model into the graph, rendering each edge accessible exclusively at specific points in time. This not only alters the underlying assumptions of regular graphs but also substantially increases the complexity of path problems and reachability. In turn, a temporal graph is often a much more realistic and accurate representation of a real-world network. In this thesis we provide a definition for a shortcut set in a temporal graph and explore differences to classic shortcut sets. Utilizing this definition, we show that temporal and regular shortcut sets yield the same results on temporal paths, enabling the application of existing construction algorithms for static shortcut sets on paths. The primary contribution of this thesis is a translation approach for general temporal graphs that utilizes the static expansion of a temporal graph, allowing the conversion of static shortcut sets into temporal shortcut sets, yielding similar results.


翻译:暂无翻译

0
下载
关闭预览

相关内容

FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
34+阅读 · 2019年10月18日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
60+阅读 · 2019年10月17日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
STRCF for Visual Object Tracking
统计学习与视觉计算组
15+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
12+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
2+阅读 · 2014年12月31日
Arxiv
31+阅读 · 2021年6月30日
Adversarial Mutual Information for Text Generation
Arxiv
13+阅读 · 2020年6月30日
Exploring Visual Relationship for Image Captioning
Arxiv
15+阅读 · 2018年9月19日
Arxiv
26+阅读 · 2018年2月27日
VIP会员
相关资讯
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
STRCF for Visual Object Tracking
统计学习与视觉计算组
15+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
12+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
相关论文
Arxiv
31+阅读 · 2021年6月30日
Adversarial Mutual Information for Text Generation
Arxiv
13+阅读 · 2020年6月30日
Exploring Visual Relationship for Image Captioning
Arxiv
15+阅读 · 2018年9月19日
Arxiv
26+阅读 · 2018年2月27日
相关基金
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
2+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员