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

DOI10.1007/978-3-030-83508-8_32MaRDI QIDQ832889zbMATH OpenOpenAlexFDO

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

Publication date 25 March 2022

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

zbMATH Keywords

approximation algorithmsgraph algorithmsfixed-parameter tractabilitygraph minorkernelizationroad networksminor-free graphs

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3946182 (Why is no real title available?)
• scientific article; zbMATH DE number 3750313 (Why is no real title available?)
• scientific article; zbMATH DE number 16297 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 7650287 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A Theorem on Planar Graphs
• A linear-time algorithm to find a separator in a graph excluding a minor
• A polynomial sized kernel for tracking paths problem
• A separator theorem for graphs of bounded genus
• Almost optimal set covers in finite VC-dimension
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Bidimensionality: new connections between FPT algorithms and PTASs
• Diameter and treewidth in minor-closed graph families
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Homomorphiesätze für Graphen
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Planar separators and parallel polygon triangulation.
• Polynomial Time Algorithms for Tracking Path Problems
• Reduced constants for simple cycle graph separation
• The design of approximation algorithms
• Tracking paths
• Tracking routes in communication networks
• -nets and simplex range queries

Cited in

(4)

• Constant factor approximation for tracking paths and fault tolerant feedback vertex set
• Constant factor approximation for tracking paths and fault tolerant feedback vertex set
• Improved kernels for tracking paths
• Polynomial kernels for tracking shortest paths

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

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