Invited paper: Simple, strict, proper, happy: a study of reachability in temporal graphs

DOI10.1007/978-3-031-21017-4_1zbMATH Open1522.68386arXiv2208.01720OpenAlexW4312714024MaRDI QIDQ6155232FDOQ6155232

Writika Sarkar, Timothée Corsini, Arnaud Casteigts

Publication date: 12 June 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Dynamic networks are a complex topic. Not only do they inherit the complexity of static networks (as a particular case) while making obsolete many techniques for these networks; they also happen to be deeply sensitive to specific definitional subtleties, such as strictness (can several consecutive edges be used at the same time instant?), properness (can adjacent edges be present at the same time?) and simpleness (can an edge be present more than once?). These features, it turns out, have a significant impact on the answers to various questions, which is a frequent source of confusion and incomparability among results. In this paper, we explore the impact of these notions, and of their interactions, in a systematic way. Our conclusions show that these aspects really matter. In particular, most of the combinations of the above properties lead to distinct levels of expressivity of a temporal graph in terms of reachability. Then, we advocate the study of an extremely simple model -- happy graphs -- where all these distinctions vanish. Happy graphs suffer from a loss of expressivity; yet, we show that they remain expressive enough to capture (and strengthen) interesting features of general temporal graphs. A number of questions are proposed to motivate the study of these objects further.

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

Recommendations

• An introduction to temporal graphs: an algorithmic perspective
• An introduction to temporal graphs: an algorithmic perspective
• Connectivity and inference problems for temporal networks
• The complexity of finding small separators in temporal graphs
• Optimizing reachability sets in temporal graphs by delaying

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs
• Some Combinatorial Theorems on Monotonicity
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Connectivity and inference problems for temporal networks
• Minimum weight paths in time-dependent networks
• Title not available (Why is that?)
• Temporal flows in temporal networks
• Parsimonious flooding in dynamic graphs
• Exploration of Constantly Connected Dynamic Graphs Based on Cactuses
• A Problem with Telephones
• Temporal graph classes: a view through temporal separators
• A connectivity model for agreement in dynamic systems
• On computing Pareto optimal paths in weighted time-dependent networks
• The complexity of optimal design of temporally connected graphs
• Finding temporal paths under waiting time constraints
• Temporal cliques admit sparse spanners
• On the Size and the Approximability of Minimum Temporally Connected Subgraphs
• The Complexity of Data Aggregation in Static and Dynamic Wireless Sensor Networks
• Distributed exploration of dynamic rings
• Title not available (Why is that?)
• Exploration of \(k\)-edge-deficient temporal graphs

Cited In (3)

• On computing large temporal (unilateral) connected components
• Title not available (Why is that?)
• On computing large temporal (unilateral) connected components

This page was built for publication: Invited paper: Simple, strict, proper, happy: a study of reachability in temporal graphs

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