On the expressivity of time-varying graphs

DOI10.1016/J.TCS.2015.04.004MaRDI QIDQ2348032zbMATH OpenOpenAlexFDO

Authors Arnaud Casteigts, P. Flocchini, Emmanuel Godard, N. Santoro, Masafumi Yamashita

Publication date 10 June 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.04.004

zbMATH Keywords

automatabufferingdynamic networksexpressivity of TVGstime-varying graphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Expressivity of Time-Varying Graphs
• Brief announcement: Waiting in dynamic networks
• On the exploration of time-varying networks
• Deterministic computations in time-varying graphs: broadcasting under unstructured mobility
• Components in time-varying graphs

Cites work

• A characterization of dynamic networks where consensus is solvable
• A theory of timed automata
• Causality, influence, and computation in possibly disconnected synchronous dynamic networks
• Characterizing topological assumptions of distributed algorithms in dynamic networks
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Coordinated consensus in dynamic networks
• Deterministic computations in time-varying graphs: broadcasting under unstructured mobility
• Distributed computation in dynamic networks
• DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
• Dynamic graph models
• Efficient routing in carrier-based mobile networks
• Exploration of constantly connected dynamic graphs based on cactuses
• Flooding time of edge-Markovian evolving graphs
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• scientific article; zbMATH DE number 3198033 (Why is no real title available?)
• Measuring Temporal Lags in Delay-Tolerant Networks
• On quasi orders of words and the confluence property
• On regularity of context-free languages
• On the complexity of information spreading in dynamic networks
• On the exploration of time-varying networks
• Ordering by Divisibility in Abstract Algebras
• Parsimonious flooding in dynamic graphs
• Searching for black holes in subways

Cited in

(10)

• Finding temporal paths under waiting time constraints
• How fast can we reach a target vertex in stochastic temporal graphs?
• Expressivity of Time-Varying Graphs
• Symbolically Bounding the Drift in Time-Constrained MSC Graphs
• Robust Time-Varying Undirected Graphs
• How fast can we reach a target vertex in stochastic temporal graphs?
• Brief announcement: Waiting in dynamic networks
• A topological perspective on distributed network algorithms
• Finding Temporal Paths Under Waiting Time Constraints.
• A general label setting algorithm and tractability analysis for the multiobjective temporal shortest path problem

This page was built for publication: On the expressivity of time-varying graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2348032)