Resolving Sets in Temporal Graphs

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Resolving Sets in Temporal Graphs

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10101 - Pure mathematics

Project

—

Continuities

R - Projekt Ramcoveho programu EK

Publication year

2024

Confidentiality

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

Article name in the collection

COMBINATORIAL ALGORITHMS, IWOCA 2024

ISBN

978-3-031-63020-0

ISSN

0302-9743

e-ISSN

1611-3349

Number of pages

14

Pages from-to

287-300

Publisher name

SPRINGER INTERNATIONAL PUBLISHING AG

Place of publication

CHAM

Event location

Ischia

Event date

Jul 1, 2024

Type of event by nationality

EUR - Evropská akce

UT code for WoS article

001282050500022