Tracking paths

DOI10.1016/J.DAM.2019.11.013MaRDI QIDQ2185723zbMATH OpenOpenAlexFDO

Authors Aritra Banik, Matthew J. Katz, Eli Packer, Marina Simakov

Publication date 5 June 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2019.11.013

zbMATH Keywords

shortest pathstarget trackingguardingtracking paths

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Distance in graphs (05C12) Paths and cycles (05C38)

Recommendations

• Tracking paths
• Tracking routes in communication networks
• A polynomial sized kernel for tracking paths problem
• A polynomial sized kernel for tracking paths problem
• Fixed-parameter tractable algorithms for tracking shortest paths

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A new approach to the minimum cut problem
• Computational geometry. Algorithms and applications.
• On the hardness of approximating minimum vertex cover

Cited in

(17)

• Fixed-parameter tractable algorithms for tracking set problems
• A polynomial sized kernel for tracking paths problem
• Tracking routes in communication networks
• Distance-based (and path-based) covering problems for graphs of given cyclomatic number
• On a method of pursuit in ``tracks
• Constant factor approximation for tracking paths and fault tolerant feedback vertex set
• Polynomial time algorithms for tracking path problems
• Tracking paths
• Finding tracks detected by a drift tube system
• Constant factor approximation for tracking paths and fault tolerant feedback vertex set
• A polynomial sized kernel for tracking paths problem
• The parameterized complexity of maximum betweenness centrality
• Improved kernels for tracking paths
• Trail saving on backtrack
• Steps and traces
• Walking through waypoints
• Polynomial kernels for tracking shortest paths

This page was built for publication: Tracking paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2185723)