Robustness: a new form of heredity motivated by dynamic networks

DOI10.1016/J.TCS.2019.08.008zbMATH Open1436.68223arXiv1905.04106OpenAlexW2970164133MaRDI QIDQ2285145FDOQ2285145

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)

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.

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

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

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)

Cites Work

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

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)