Robustness: a new form of heredity motivated by dynamic networks

DOI10.1016/J.TCS.2019.08.008MaRDI QIDQ2285145zbMATH OpenOpenAlexFDO

Authors Arnaud Casteigts, Swan Dubois, Franck Petit, John Michael Robson

Publication date 16 January 2020

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

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

zbMATH Keywords

heredity in graphshighly dynamic networksminimal independent setstemporal covering structure

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We investigate a special case of hereditary property in graphs, referred to as {em robustness}. A property (or structure) is called robust in a graph $G$ if it is inherited by all the connected spanning subgraphs of $G$. We motivate this definition using two different settings of dynamic networks. The first corresponds to networks of low dynamicity, where some links may be permanently removed so long as the network remains connected. The second corresponds to highly-dynamic networks, where communication links appear and disappear arbitrarily often, subject only to the requirement that the entities are temporally connected in a recurrent fashion ({it i.e.} they can always reach each other through temporal paths). Each context induces a different interpretation of the notion of robustness. We start by motivating the definition and discussing the two interpretations, after what we consider the notion independently from its interpretation, taking as our focus the robustness of {em maximal independent sets} (MIS). A graph may or may not admit a robust MIS. We characterize the set of graphs forallMIS in which {em all} MISs are robust. Then, we turn our attention to the graphs that {em admit} a robust MIS (existsMIS). This class has a more complex structure; we give a partial characterization in terms of elementary graph properties, then a complete characterization by means of a (polynomial time) decision algorithm that accepts if and only if a robust MIS exists. This algorithm can be adapted to construct such a solution if one exists.

Recommendations

• scientific article; zbMATH DE number 1759469
• On the robustness of interconnections in random graphs: a symbolic approach.
• Characterization of robustness and resilience in graphs: a mini-review
• \(k\)-robust single-message transmission
• Optimal dynamic distributed MIS

Cites work

• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 970795 (Why is no real title available?)
• A survey of hereditary properties of graphs
• Complex networks. Structure, robustness and function.
• Connectivity and inference problems for temporal networks
• Efficient Deterministic Distributed Coloring with Small Bandwidth
• Enabling minimal dominating set in highly dynamic distributed systems
• Enumerating maximal cliques in link streams with durations
• On cliques in graphs
• Temporal vertex cover with a sliding time window
• The number of maximal independent sets in a connected graph
• The number of maximal independent sets in connected graphs

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Robustness: a new form of heredity motivated by dynamic networks

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