A study of connectivity on dynamic graphs: computing persistent connected components

DOI10.1007/S10288-022-00507-3MaRDI QIDQ6097848zbMATH OpenFDO

Authors Mathilde Vernet, Yoann Pigné, Eric Sanlaville

Publication date 7 June 2023

Published in 4OR (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10288-022-00507-3

zbMATH Keywords

connectivitydynamic graphsonline algorithmpersistent connected component

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Recommendations

• Efficiently testing T-interval connectivity in dynamic graphs
• Static and dynamic parallel computation of connected components
• Real-time monitoring of undirected networks: articulation points, bridges, and connected and biconnected components
• Dynamic connectivity in digital images
• Algorithms on evolving graphs

Cites work

• A connectivity model for agreement in dynamic systems
• An introduction to temporal graphs: an algorithmic perspective
• Collective dynamics of `small-world' networks
• Components in time-varying graphs
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Connectivity and inference problems for temporal networks
• Efficiently testing T-interval connectivity in dynamic graphs
• Graphs and algorithms in communication networks. Studies in broadband, optical, wireless and ad hoc networks
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• On verifying and maintaining connectivity of interval temporal networks
• Statistical mechanics of complex networks
• The Structure and Function of Complex Networks

Cited in

(9)

• A topological approach to dynamic graph connectivity
• Components in time-varying graphs
• Real-time monitoring of undirected networks: articulation points, bridges, and connected and biconnected components
• Efficiently testing T-interval connectivity in dynamic graphs
• On persistent directed graphs
• On computing large temporal (unilateral) connected components
• Temporally connected components
• The dynamic Steiner tree problem: definitions, complexity, algorithms
• The shortest temporal exploration problem

This page was built for publication: A study of connectivity on dynamic graphs: computing persistent connected components

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