Resolving Sets in Temporal Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10488013" target="_blank" >RIV/00216208:11320/24:10488013 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-63021-7_22" target="_blank" >https://doi.org/10.1007/978-3-031-63021-7_22</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-63021-7_22" target="_blank" >10.1007/978-3-031-63021-7_22</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Resolving Sets in Temporal Graphs

Popis výsledku v původním jazyce

A resolving set R in a graph G is a set of vertices such that every vertex of G is uniquely identified by its distances to the vertices of R. Introduced in the 1970&apos;s, this concept has been since then extensively studied from both combinatorial and algorithmic point of view. We propose a generalization of the concept of resolving sets to temporal graphs, i.e., graphs with edge sets that change over discrete time-steps. In this setting, the temporal distance from u to v is the earliest possible time-step at which a journey with strictly increasing time-steps on edges leaving u reaches v, i.e., the first time-step at which v could receive a message broadcast from u. A temporal resolving set of a temporal graph G is a subset R of its vertices such that every vertex of G is uniquely identified by its temporal distances from vertices of R. We study the problem of finding a minimum-size temporal resolving set, and show that it is NP-complete even on very restricted graph classes and with strong constraints on the time-steps: temporal complete graphs where every edge appears in either time-step 1 or 2, temporal trees where every edge appears in at most two consecutive time-steps, and even temporal subdivided stars where every edge appears in at most two (not necessarily consecutive) time-steps. On the other hand, we give polynomial-time algorithms for temporal paths and temporal stars where every edge appears in exactly one time-step, and give a combinatorial analysis and algorithms for several temporal graph classes where the edges appear in periodic time-steps.

Název v anglickém jazyce

Resolving Sets in Temporal Graphs

Popis výsledku anglicky

A resolving set R in a graph G is a set of vertices such that every vertex of G is uniquely identified by its distances to the vertices of R. Introduced in the 1970&apos;s, this concept has been since then extensively studied from both combinatorial and algorithmic point of view. We propose a generalization of the concept of resolving sets to temporal graphs, i.e., graphs with edge sets that change over discrete time-steps. In this setting, the temporal distance from u to v is the earliest possible time-step at which a journey with strictly increasing time-steps on edges leaving u reaches v, i.e., the first time-step at which v could receive a message broadcast from u. A temporal resolving set of a temporal graph G is a subset R of its vertices such that every vertex of G is uniquely identified by its temporal distances from vertices of R. We study the problem of finding a minimum-size temporal resolving set, and show that it is NP-complete even on very restricted graph classes and with strong constraints on the time-steps: temporal complete graphs where every edge appears in either time-step 1 or 2, temporal trees where every edge appears in at most two consecutive time-steps, and even temporal subdivided stars where every edge appears in at most two (not necessarily consecutive) time-steps. On the other hand, we give polynomial-time algorithms for temporal paths and temporal stars where every edge appears in exactly one time-step, and give a combinatorial analysis and algorithms for several temporal graph classes where the edges appear in periodic time-steps.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

R - Projekt Ramcoveho programu EK

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

COMBINATORIAL ALGORITHMS, IWOCA 2024

ISBN

978-3-031-63020-0

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

14

Strana od-do

287-300

Název nakladatele

SPRINGER INTERNATIONAL PUBLISHING AG

Místo vydání

CHAM

Místo konání akce

Ischia

Datum konání akce

1. 7. 2024

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

001282050500022