Sharp Thresholds in Random Simple Temporal Graphs
From MaRDI portal
Publication:6131198
DOI10.1137/22m1511916arXiv2011.03738OpenAlexW3098783518MaRDI QIDQ6131198
Michael Raskin, Malte Renken, Arnaud Casteigts, Victor Zamaraev
Publication date: 4 April 2024
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2011.03738
sharp thresholdErdős-Renyi random graphedge-ordered graphtemporal reachabilitygossiping protocolrandom temporal graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parsimonious flooding in dynamic graphs
- Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
- Broadcasting in dynamic radio networks
- The shortest-path problem for graphs with random arc-lengths
- A strong-connectivity algorithm and its applications in data flow analysis
- Finding temporal paths under waiting time constraints
- Temporal vertex cover with a sliding time window
- Sliding window temporal graph coloring
- Temporal cliques admit sparse spanners
- Reachability and expectation in gossiping
- How fast can we reach a target vertex in stochastic temporal graphs?
- Nearly-linear monotone paths in edge-ordered graphs
- Assigning times to minimise reachability in temporal graphs
- The complexity of optimal design of temporally connected graphs
- Weighted sums of certain dependent random variables
- Increasing paths in edge ordered graphs
- Increasing Hamiltonian paths in random edge orderings
- Flooding time in edge-Markovian dynamic graphs
- Introduction to Random Graphs
- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
- A Problem with Telephones
- On the Size and the Approximability of Minimum Temporally Connected Subgraphs
- One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
- Evolving graphs: dynamical models, inverse problems and propagation
- Probabilistic Analysis of Rumor-Spreading Time
- Temporal Network Theory
- Long Monotone Trails in Random Edge-Labellings of Random Graphs
- Most edge‐orderings of Kn have maximal altitude
- Computation in networks of passively mobile finite-state sensors
- Some Combinatorial Theorems on Monotonicity
- COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
- Computing maximum matchings in temporal graphs.
- Connectivity and inference problems for temporal networks
- Random exchanges of information
- Random exchanges of information
- Temporal graph classes: a view through temporal separators
