Polynomial Time Algorithms for Tracking Path Problems
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F22%3A00358547" target="_blank" >RIV/68407700:21240/22:00358547 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/s00453-022-00931-1" target="_blank" >https://doi.org/10.1007/s00453-022-00931-1</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00453-022-00931-1" target="_blank" >10.1007/s00453-022-00931-1</a>
Alternative languages
Result language
angličtina
Original language name
Polynomial Time Algorithms for Tracking Path Problems
Original language description
Given a graph G, and terminal vertices s and t, the Tracking Paths problem asks to compute a set of minimum number of vertices to be marked as trackers, such that the sequence of trackers encountered in each s-t path is unique. Tracking Paths is NP-hard in both directed and undirected graphs in general. In this paper we give a collection of polynomial time algorithms for some restricted versions of Tracking Paths. We prove that Tracking Paths is polynomial time solvable for undirected chordal graphs and tournament graphs. We also show that Tracking Paths is NP-hard in graphs with bounded maximum degree Δ >= 6 , and give a 2 (Δ + 1) -approximate algorithm for this case. Further, we give a polynomial time algorithm which, given an undirected graph G, a tracking set T? V(G) , and a sequence of trackers π, returns the unique s-t path in G that corresponds to π, if one exists. Finally we analyze the version of tracking s-t paths where paths are tracked using edges instead of vertices, and we give a polynomial time algorithm for the same.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Algorithmica
ISSN
0178-4617
e-ISSN
1432-0541
Volume of the periodical
84
Issue of the periodical within the volume
6
Country of publishing house
DE - GERMANY
Number of pages
23
Pages from-to
1548-1570
UT code for WoS article
000752837200002
EID of the result in the Scopus database
2-s2.0-85124341700