The Price of Universal Temporal Reachability
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917346990358528 |
|---|---|
| author | Bui-Xuan, Binh-Minh Nguyen, Nhat-Minh Tixeuil, Sébastien Yamauchi, Yukiko |
| author_facet | Bui-Xuan, Binh-Minh Nguyen, Nhat-Minh Tixeuil, Sébastien Yamauchi, Yukiko |
| contents | Dynamic networks are graphs in which edges are available only at specific time instants, modeling connections that change over time. The dynamic network creation game studies this setting as a strategic interaction where each vertex represents a player. Players can add or remove time-labeled edges in order to minimize their personal cost. This cost has two components: a construction cost, calculated as the number of time instants during which a player maintains edges multiplied by a constant $α$, and a communication cost, defined as the average distance to all other vertices in the network. Communication occurs through temporal paths, which are sequences of adjacent edges with strictly increasing time labels and no repeated vertices. We show for the shortest distance (minimizing the number of edges) that the price of anarchy can be proportional to the number of vertices, contrasting the constant price conjectured for static networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_15176 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Price of Universal Temporal Reachability Bui-Xuan, Binh-Minh Nguyen, Nhat-Minh Tixeuil, Sébastien Yamauchi, Yukiko Data Structures and Algorithms Dynamic networks are graphs in which edges are available only at specific time instants, modeling connections that change over time. The dynamic network creation game studies this setting as a strategic interaction where each vertex represents a player. Players can add or remove time-labeled edges in order to minimize their personal cost. This cost has two components: a construction cost, calculated as the number of time instants during which a player maintains edges multiplied by a constant $α$, and a communication cost, defined as the average distance to all other vertices in the network. Communication occurs through temporal paths, which are sequences of adjacent edges with strictly increasing time labels and no repeated vertices. We show for the shortest distance (minimizing the number of edges) that the price of anarchy can be proportional to the number of vertices, contrasting the constant price conjectured for static networks. |
| title | The Price of Universal Temporal Reachability |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.15176 |