Improved kernels for tracking paths

DOI10.1016/j.ipl.2023.106360OpenAlexW4315490332MaRDI QIDQ2681404

Venkatesh Raman, Hadi Khodabandeh, Pratibha Choudhary, Michael T. Goodrich, Pedro Matias, Siddharth Gupta

Publication date: 3 February 2023

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2023.106360

zbMATH Keywords

planar graphsgraph algorithmsfixed-parameter tractabilitykernelizationtracking paths

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Identifying path covers in graphs
• How to catch marathon cheaters: new approximation algorithms for tracking paths
• Graph minors. V. Excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Polynomial kernels for tracking shortest paths
• Tracking paths
• Fixed-parameter tractable algorithms for tracking shortest paths
• Fixed-parameter tractable algorithms for tracking set problems
• On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths
• Kernelization
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Polynomial Time Algorithms for Tracking Path Problems
• Parameterized Algorithms
• Tracking routes in communication networks
• A polynomial sized kernel for tracking paths problem
• Constant factor approximation for tracking paths and fault tolerant feedback vertex set

This page was built for publication: Improved kernels for tracking paths