Name
Abstract | ||
|---|---|---|
We investigate a special case of hereditary property in graphs, referred to as 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 (i.e. they can always reach each other through temporal paths). Each context induces a different interpretation of the notion of robustness. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.tcs.2019.08.008 | Theoretical Computer Science |
Keywords | Field | DocType |
Heredity in graphs,Highly-dynamic networks,Minimal independent sets,Temporal covering structure | Discrete mathematics,Graph,Combinatorics,Graph property,Hereditary property,Robustness (computer science),If and only if,Time complexity,Mathematics,Special case | Journal |
Volume | ISSN | Citations |
806 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arnaud Casteigts | 1 | 406 | 27.35 |
| Swan Dubois | 2 | 145 | 17.21 |
| Franck Petit | 3 | 736 | 60.02 |
| John Michael Robson | 4 | 206 | 18.23 |