How to catch marathon cheaters: new approximation algorithms for tracking paths

DOI10.1007/978-3-030-83508-8_32OpenAlexW3198204543MaRDI QIDQ832889

Siddharth Gupta, Michael T. Goodrich, Hadi Khodabandeh, Pedro Matias

Publication date: 25 March 2022

Full work available at URL: https://arxiv.org/abs/2104.12337

zbMATH Keywords

graph minorgraph algorithmsapproximation algorithmsfixed-parameter tractabilitykernelizationroad networksminor-free graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Related Items (4)

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 ⋮ Polynomial kernels for tracking shortest paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Planar separators and parallel polygon triangulation.
• \(\epsilon\)-nets and simplex range queries
• Diameter and treewidth in minor-closed graph families
• Almost optimal set covers in finite VC-dimension
• Reduced constants for simple cycle graph separation
• Homomorphiesätze für Graphen
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• The Design of Approximation Algorithms
• A separator theorem for graphs of bounded genus
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Polynomial Time Algorithms for Tracking Path Problems
• Tracking Paths
• A Theorem on Planar Graphs
• Tracking routes in communication networks
• A polynomial sized kernel for tracking paths problem

This page was built for publication: How to catch marathon cheaters: new approximation algorithms for tracking paths