Fixed-parameter tractable algorithms for tracking shortest paths

DOI10.1016/j.tcs.2020.09.006zbMath1464.68274arXiv2001.08977OpenAlexW3086608093MaRDI QIDQ2210499

Venkatesh Raman, Pratibha Choudhary, Aritra Banik, Saket Saurabh

Publication date: 6 November 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graphskernelfixed-parameter tractableset systemstracking pathsshortest \(s\)-\(t\) paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (6)

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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterizations of test cover with bounded test sizes
• Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
• Chain packing in graphs
• An efficient fixed-parameter algorithm for 3-hitting set
• A kernelization algorithm for \(d\)-hitting set
• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Parameterizing above or below guaranteed values
• Approximation algorithms for the test cover problem
• Parameterized and approximation complexity of \textsc{Partial VC Dimension}
• (Non-)existence of polynomial kernels for the test cover problem
• Identifying vertex covers in graphs
• Induced subsets
• Fixed-parameter tractable algorithms for tracking set problems
• Parameterized Study of the Test Cover Problem
• The Complexity of Enumeration and Reliability Problems
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• On a new class of codes for identifying vertices in graphs
• Parameterized Algorithms for (r,l)-Partization
• Reducibility among Combinatorial Problems
• Polynomial Time Algorithms for Tracking Path Problems
• Tracking Paths
• Parameterized Algorithms
• Tracking routes in communication networks

This page was built for publication: Fixed-parameter tractable algorithms for tracking shortest paths