Polynomial Time Algorithms for Tracking Path Problems

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Polynomial Time Algorithms for Tracking Path Problems

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Polynomial Time Algorithms for Tracking Path Problems

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

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 periodika

Algorithmica

ISSN

0178-4617

e-ISSN

1432-0541

Svazek periodika

84

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

23

Strana od-do

1548-1570

Kód UT WoS článku

000752837200002

EID výsledku v databázi Scopus

2-s2.0-85124341700