A polynomial sized kernel for tracking paths problem
From MaRDI portal
Publication:5919306
DOI10.1007/s00453-019-00602-8zbMath1436.68142OpenAlexW2955033360WikidataQ127563558 ScholiaQ127563558MaRDI QIDQ5919306
Saket Saurabh, Pratibha Choudhary, Aritra Banik, Daniel Lokshtanov, Venkatesh Raman
Publication date: 16 January 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-019-00602-8
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Polynomial Time Algorithms for Tracking Path Problems ⋮ How to catch marathon cheaters: new approximation algorithms for tracking paths ⋮ Polynomial time algorithms for tracking path problems ⋮ 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 ⋮ Polynomial kernels for tracking shortest paths
Cites Work
- Unnamed Item
- Unnamed Item
- The disjoint paths problem in quadratic time
- Faster deterministic \textsc{Feedback Vertex Set}
- Extremal graph theory for metric dimension and diameter
- Landmarks in graphs
- A 4 k 2 kernel for feedback vertex set
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Reducibility among Combinatorial Problems
- Tracking Paths
- Parameterized Algorithms