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

DOI10.4230/LIPIcs.ICALP.2019.131OpenAlexW2966256418MaRDI QIDQ5092333

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

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.131

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (2)

Computing maximum matchings in temporal graphs ⋮ Temporal vertex cover with a sliding time window

Cites Work

• Unnamed Item
• Computing maximal cliques in link streams
• Tail bounds for sums of geometric and exponential variables
• 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
• 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
• Temporal Network Optimization Subject to Connectivity Constraints
• 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