Exploration of the T-Interval-Connected Dynamic Graphs: the Case of the Ring
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | ILCINKAS, David | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Combinatoire et Algorithmique | |
| dc.contributor.author | WADE, Ahmed | |
| dc.date.accessioned | 2024-04-15T09:43:17Z | |
| dc.date.available | 2024-04-15T09:43:17Z | |
| dc.date.issued | 2013 | |
| dc.date.conference | 2013-07-01 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/197752 | |
| dc.description.abstractEn | In this paper, we study the T-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is T-interval-connected (T > 0) if, for every window of T consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman (STOC 2010). We focus on the case when the underlying graph is a ring of size n, and we show that the worst-case time complexity for the exploration problem is 2n-T-Theta(1) time units if the agent knows the dynamics of the graph, and n+ n/max{1, T-1} * (delta-1) \pm Theta(delta) time units otherwise, where delta is the maximum time between two successive appearances of an edge. | |
| dc.description.sponsorship | Calculabilité et complexité en distribué - ANR-11-BS02-0014 | |
| dc.language.iso | en | |
| dc.source.title | Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity | |
| dc.subject.en | Exploration | |
| dc.subject.en | Dynamic graphs | |
| dc.subject.en | Mobile agent | |
| dc.subject.en | T-interval-connectivity | |
| dc.title.en | Exploration of the T-Interval-Connected Dynamic Graphs: the Case of the Ring | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| dc.subject.hal | Informatique [cs]/Mathématique discrète [cs.DM] | |
| bordeaux.page | to appear | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | SIROCCO 2013 | |
| bordeaux.country | IT | |
| bordeaux.title.proceeding | Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity | |
| bordeaux.conference.city | Ischia | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00847771 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.end | 2013-07-03 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00847771v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Proceedings%20of%20the%2020th%20International%20Colloquium%20on%20Structural%20Information%20and%20Communication%20Complexity&rft.date=2013&rft.spage=to%20appear&rft.epage=to%20appear&rft.au=ILCINKAS,%20David&WADE,%20Ahmed&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||