Temporally connected components

DOI10.1016/J.TCS.2024.114757MaRDI QIDQ6612544zbMATH OpenFDO

Authors Stefan Balev, Eric Sanlaville, Jason Schoeters

Publication date 1 October 2024

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

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114757

zbMATH Keywords

\(\mathrm{N}\)P-complete problemsalgorithmconnected componentpolynomial-time reductiontemporal connectivitytemporal graph theory

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A connectivity model for agreement in dynamic systems
• A Graph Model for Fault-Tolerant Computing Systems
• A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
• A study of connectivity on dynamic graphs: computing persistent connected components
• Algorithms on evolving graphs
• Components in time-varying graphs
• Computing maximum matchings in temporal graphs.
• Computing parameters of sequence-based dynamic graphs
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Dynamic evolution of shipping network based on hypergraph
• Efficient continuous-time dynamic network flow algorithms
• Exploration of constantly connected dynamic graphs based on cactuses
• Extended Abstracts EuroComb 2021
• Gossips and telephones
• Graph theory
• Label-connected graphs and the gossip problem
• Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks
• On cliques in graphs
• On computing large temporal (unilateral) connected components
• On verifying and maintaining connectivity of interval temporal networks
• Temporal cliques admit sparse spanners
• The complexity of determining the rainbow vertex-connection of a graph
• The complexity of finding small separators in temporal graphs
• The complexity of optimal design of temporally connected graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• The State of the Art in Dynamic Graph Algorithms

Cited in

(4)

• Temporal reachability dominating sets: contagion in temporal graphs
• Temporal connectivity: coping with foreseen and unforeseen delays
• The dynamic Steiner tree problem: definitions, complexity, algorithms
• The shortest temporal exploration problem

This page was built for publication: Temporally connected components

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