A polynomial sized kernel for tracking paths problem

DOI10.1007/S00453-019-00602-8MaRDI QIDQ5919306zbMATH OpenOpenAlexWikidataFDO

Authors Aritra Banik, Pratibha Choudhary, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh

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

zbMATH Keywords

feedback vertex setFPTgraphkernelparameterized complexitys-t pathstracking paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• A polynomial sized kernel for tracking paths problem
• Fixed-parameter tractable algorithms for tracking shortest paths
• Tracking paths
• Fixed-parameter tractable algorithms for tracking set problems
• Tracking paths

Cites work

• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A 4k^2 kernel for feedback vertex set
• Extremal graph theory for metric dimension and diameter
• Faster deterministic \textsc{Feedback Vertex Set}
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• Landmarks in graphs
• Parameterized algorithms
• Reducibility among combinatorial problems
• The disjoint paths problem in quadratic time
• Tracking paths

Cited in

(12)

• Structural parameterizations of Tracking Paths problem
• Polynomial kernels for tracking shortest paths
• Polynomial time algorithms for tracking path problems
• Tracking paths
• Fixed-parameter tractable algorithms for tracking set problems
• Improved kernels for tracking paths
• Polynomial Time Algorithms for Tracking Path Problems
• 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
• A polynomial sized kernel for tracking paths problem
• How to catch marathon cheaters: new approximation algorithms for tracking paths

This page was built for publication: A polynomial sized kernel for tracking paths problem

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