在时间图表中的不安可达性问题
Suhas Thejaswi1, Juho Lauri2, Aristides Gionis3
1Max Planck Institute for Software Systems, Kaiserslautern, Germany.
Knowledge and information systems
|June 19, 2025
概括
这项研究引入了一个新的框架,用于解决时间图中的不安可访问性问题,使得复杂的网络动态,如疾病传播和接触者追踪,能够有效地分析.
科学领域:
- 图形理论和算法
- 网络科学 网络科学
- 计算复杂性 计算复杂性
背景情况:
- 时间图可以模拟连接随时间变化的动态网络.
- 与等待时间限制相关的可访问性问题对于分析现实世界中的疾病传播和信息传播等过程至关重要.
- 现有的方法难以应对时间图的复杂性和顶点着色约束.
研究的目的:
- 开发一个高效的算法框架,以解决时间和顶点颜色的时间图中不停的可访问性问题.
- 分析这些问题的时间和空间复杂性,特别是在路径长度和休息时间方面.
- 为实际应用提供最佳和可扩展的解决方案,包括疾病传播和网络分析.
主要方法:
- 提出了一个基于受约束的多线性选的代数算法框架.
- 使用参数化的复杂性分析,重点关注路径长度 (k) 和最大休息时间 (Δ).
- 开发了一个开源实现,并在合成和现实世界数据集上严格测试.
主要成果:
- 提出的问题可以在O(2^k * k * m * Δ) 时间和O(n * Δ) 空间中解决,参数为路径长度k.
- 对顶点颜色时间图的算法在合理的复杂性假设下被证明是最佳的.
- 该实现展示了高达10亿个时间边缘的图形的可扩展性,有效地解决复杂的问题.
结论:
- 开发的框架在解决时间网络中不停的可访问性问题方面取得了重大进展.
- 这些算法是高效的,可扩展的,对于顶点颜色的时间图是最佳的,提供了实际的解决方案.
- 开源实现促进了在流行病学和网络分析等多个领域的进一步研究和应用.
更多相关视频
10:44Inherent Dynamics Visualizer, an Interactive Application for Evaluating and Visualizing Outputs from a Gene Regulatory Network Inference Pipeline
Published on: December 7, 2021
2.3K
10:51Frame-by-Frame Video Analysis of Idiosyncratic Reach-to-Grasp Movements in Humans
Published on: January 15, 2018
8.5K
相关概念视频
01:26Constraints and Statical Determinacy
705
In structural engineering, the equilibrium of a system is not only determined by its equations of equilibrium but also with the help of constraints. Constraints refer to restrictions on the motion of a system. The proper combinations of constraints can minimize the total number of constraints needed to maintain a system in mechanical equilibrium. When this happens, the system is said to be statically determinate. For such systems, the unknown reaction supports can be estimated using equilibrium...
705
01:13Stability of Equilibrium Configuration: Problem Solving
678
The stability of equilibrium configurations is an important concept in physics, engineering, and other related fields. In simple terms, it refers to the tendency of an object or system to return to its equilibrium position after being disturbed. The stability of an equilibrium configuration can be analyzed by considering the potential energy function of the system and examining its behavior near the equilibrium point.
Problem-solving in the context of the stability of equilibrium configuration...
Problem-solving in the context of the stability of equilibrium configuration...
678
01:14Stability of structures
258
In mechanical engineering, the stability of systems under various forces is critical for designing durable and efficient structures. One fundamental way to explore these concepts is by analyzing systems like two rods connected at a pivot point, O, with a torsional spring of spring constant k at the pivot point. This system is similar in appearance to a scissor jack used to change tires on a car. In this case, the arms of the linkage (equivalent to the rods in this system) are entirely vertical,...
258
01:16Statically Indeterminate Problem Solving
505
Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
505
01:15Thevinin's Theorem
806
Thévenin's theorem plays a pivotal role in electrical circuit analysis, offering a solution to the challenges posed by variable loads within a circuit. In practical applications, it is common to encounter circuits where certain elements remain fixed while others fluctuate, often referred to as the "load." A typical household electrical outlet serves as a prime example of a variable load, as it can be connected to a variety of appliances, each with its own unique electrical...
806
01:24Normal and Tangetial Components: Problem Solving
231
Consider a man with a mass of 70 kg seated in a chair connected to a pin support through a member BC. If the man maintains an upright position, the task is to determine the horizontal and vertical reactions of the chair on the man when the member makes a 45° angle with the horizontal. At this moment, the man has a speed of 5 m/s, increasing at a rate of 1 m/s².
231