Fixed-parameter tractable algorithms for tracking shortest paths
From MaRDI portal
Publication:2210499
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
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