计数时间路径
Jessica Enright1, Kitty Meeks1, Hendrik Molter2
1School of Computing Science, University of Glasgow, Glasgow, UK.
概括
这项研究探讨了计数时间路径的复杂性,这对于时间间的中心性至关重要. 我们展示了这个问题通常很难,但为特定情况下提供了准确和近似的算法.
科学领域:
- 图形理论 图形理论
- 计算复杂性 计算复杂性
- 网络分析 网络分析
背景情况:
- 时间图表模拟动态网络,连接性随着时间的推移而变化.
- 中间中心性是识别网络中具有影响力的节点的关键指标.
- 计算时间间的中心性依赖于计数时间路径.
研究的目的:
- 调查计数时间路径 (#时间路径) 的参数化复杂性.
- 分析#Temporal Path的计算硬度和近似极限.
- 在特定的图形结构中为#Temporal Path开发精确和近似的算法.
主要方法:
- 使用反顶数进行参数化复杂性分析.
- 计算时间路径的近似算法设计.
- 减少中间的中心性问题,以#时间路径.
主要成果:
- # 时间路径可能与反顶数相比不是固定参数可处理 (FPT).
- 这个问题通常很难近似.
- 针对特定情况下,开发了几种精确和近似的FPT算法.
结论:
- 计数时间路径在计算上具有挑战性,特别是在一般时间图中.
- 参数化的复杂性提供了一个框架,以理解和减轻#Temporal Path的硬度.
- 开发的算法为特定的网络分析场景提供了实际解决方案.
相关概念视频
Interference: Path Lengths
1.2K
Consider two sources of sound, that may or may not be in phase, emitting waves at a single frequency, and consider the frequencies to be the same.
Two special sources may be considered when they are in phase. This can be easily achieved by feeding the two sources from the same source. An example would be synchronizing the two speakers by feeding them with the same source, such as the sound waves produced by a tuning fork. This setup ensures that the two sources have the same frequency and are...
Two special sources may be considered when they are in phase. This can be easily achieved by feeding the two sources from the same source. An example would be synchronizing the two speakers by feeding them with the same source, such as the sound waves produced by a tuning fork. This setup ensures that the two sources have the same frequency and are...
1.2K
Indirect Motor Pathways
1.3K
The indirect motor or extrapyramidal pathways originate in the brainstem, the lower portion of the brain that connects it to the spinal cord. They consist of several distinct tracts, each with specialized functions. The four main tracts of the indirect motor pathways are the vestibulospinal tract, the reticulospinal tract, the tectospinal tract, and the rubrospinal tract.
The vestibulospinal tract originates in the vestibular nuclei of the brainstem. The vestibular system detects changes in...
The vestibulospinal tract originates in the vestibular nuclei of the brainstem. The vestibular system detects changes in...
1.3K
Adjusting a Traverse
37
In the site survey of a four-sided traverse, internal angles are essential to ensure geometric accuracy. The survey revealed that the sum of the measured internal angles was 359 degrees and 48 minutes, which is 12 minutes less than the expected 360 degrees. This discrepancy signals an error likely arising from measurement inaccuracies during the fieldwork.To rectify this error, the adjustment process involved distributing the 12-minute shortfall equally across the four internal angles. By...
37
Survival Tree
44
Survival trees are a non-parametric method used in survival analysis to model the relationship between a set of covariates and the time until an event of interest occurs, often referred to as the "time-to-event" or "survival time." This method is particularly useful when dealing with censored data, where the event has not occurred for some individuals by the end of the study period, or when the exact time of the event is unknown.
Building a Survival Tree
Constructing a...
Building a Survival Tree
Constructing a...
44
Direct Motor Pathways
1.7K
The direct motor pathways, also known as the pyramidal tracts, are a group of neural pathways that originate in the brain and descend through the spinal cord. They control the voluntary movement of the body. There are two major direct motor pathways: the corticospinal and the corticobulbar tracts.
The corticospinal tract is responsible for the voluntary movement of the limbs and trunk. It originates in the cerebral cortex of the brain and descends through the cerebrum's internal capsule and...
The corticospinal tract is responsible for the voluntary movement of the limbs and trunk. It originates in the cerebral cortex of the brain and descends through the cerebrum's internal capsule and...
1.7K
Propagation of Action Potentials
4.8K
The propagation of an action potential refers to the process by which a nerve impulse, or "action potential," travels along a neuron.
Neurons (nerve cells) have a resting membrane potential, with a slightly negative charge inside compared to outside. This is maintained by ion channels, such as sodium (Na+) and potassium (K+) channels, which control the flow of ions. When a stimulus, like a touch or a signal from another neuron, triggers the neuron, sodium channels open, allowing sodium...
Neurons (nerve cells) have a resting membrane potential, with a slightly negative charge inside compared to outside. This is maintained by ion channels, such as sodium (Na+) and potassium (K+) channels, which control the flow of ions. When a stimulus, like a touch or a signal from another neuron, triggers the neuron, sodium channels open, allowing sodium...
4.8K


