How fast can we reach a target vertex in stochastic temporal graphs?

DOI10.1016/j.jcss.2020.05.005zbMath1456.68124arXiv1903.03636OpenAlexW3027725861MaRDI QIDQ2194859

George B. Mertzios, Eleni C. Akrida, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Victor Zamaraev, Paul G. Spirakis

Publication date: 7 September 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1903.03636

zbMATH Keywords

polynomial-time approximation schemetemporal network\#P-hard problemstochastic temporal graphtemporal path

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (9)

Deleting edges to restrict the size of an epidemic in temporal networks ⋮ Sharp Thresholds in Random Simple Temporal Graphs ⋮ Disentangling the computational complexity of network untangling ⋮ Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs ⋮ Finding temporal paths under waiting time constraints ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Unnamed Item ⋮ Edge exploration of temporal graphs ⋮ Edge exploration of temporal graphs

Uses Software

• cliques

Cites Work

• Unnamed Item
• Unnamed Item
• Computing maximal cliques in link streams
• Tail bounds for sums of geometric and exponential variables
• Temporal network optimization subject to connectivity constraints
• On the exploration of time-varying networks
• Cover time in edge-uniform stochastically-evolving graphs
• On the expressivity of time-varying graphs
• The complexity of optimal design of temporally connected graphs
• On temporal graph exploration
• DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
• Flooding Time of Edge-Markovian Evolving Graphs
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• On Spreading a Rumor
• The Recognition of Series Parallel Digraphs
• Markov Chains
• Temporal Vertex Cover with a Sliding Time Window
• Distributed shortest-path protocols for time-dependent networks
• Fibonacci heaps and their uses in improved network optimization algorithms
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Connectivity and inference problems for temporal networks

This page was built for publication: How fast can we reach a target vertex in stochastic temporal graphs?