Tracking routes in communication networks

DOI10.1016/J.TCS.2020.07.012zbMath1467.68135OpenAlexW2957826768MaRDI QIDQ5918972

Guido Proietti, Davide Bilò, Stefano Leucci, Luciano Gualà

Publication date: 21 October 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.07.012

zbMATH Keywords

shortest pathsapproximation algorithmsNP-hardnesstracking set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Communication networks in operations research (90B18) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (5)

How to catch marathon cheaters: new approximation algorithms for tracking paths ⋮ Improved kernels for tracking paths ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Structural parameterizations of Tracking Paths problem

Cites Work

• Unnamed Item
• Network verification via routing table queries
• Landmarks in graphs
• Fixed-parameter tractable algorithms for tracking set problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Planar Formulae and Their Uses
• Tracking Paths
• A polynomial sized kernel for tracking paths problem

This page was built for publication: Tracking routes in communication networks