Fixed-parameter tractable algorithms for tracking shortest paths
type: Item
instance of: scholarly article
title: Fixed-parameter tractable algorithms for tracking shortest paths
zbMATH Open document ID: 1464.68274
author: Aritra Banik
author: Pratibha Choudhary
author: Venkatesh Raman
author: Saket Saurabh
published in: Theoretical Computer Science
publication date: 2020-11-06T00:00:00Z
full work available at URL: https://arxiv.org/abs/2001.08977
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68Q27
zbMATH DE Number: 7270949
zbMATH Keywords: graphs
zbMATH Keywords: shortest \(s\)-\(t\) paths
zbMATH Keywords: tracking paths
zbMATH Keywords: fixed-parameter tractable
zbMATH Keywords: kernel
zbMATH Keywords: set systems
MaRDI profile type: Publication
OpenAlex ID: W3086608093
arXiv ID: 2001.08977
cites work: Fixed-parameter tractable algorithms for tracking set problems
cites work: Tracking Paths
cites work: Reducibility among Combinatorial Problems
cites work: Identifying vertex covers in graphs
cites work: Chain packing in graphs
cites work: Parameterized Algorithms
cites work: Parameterized and approximation complexity of \textsc{Partial VC Dimension}
cites work: Parameterized Study of the Test Cover Problem
cites work: Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
cites work: Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
cites work: Q4502621
cites work: On a new class of codes for identifying vertices in graphs
cites work: Q5875621
cites work: Tracking routes in communication networks
cites work: Polynomial Time Algorithms for Tracking Path Problems
cites work: A kernelization algorithm for \(d\)-hitting set
cites work: An efficient fixed-parameter algorithm for 3-hitting set
cites work: Q4393480
cites work: Q4411361
cites work: Approximation algorithms for the test cover problem
cites work: Q4796174
cites work: (Non-)existence of polynomial kernels for the test cover problem
cites work: Parameterizations of test cover with bounded test sizes
cites work: Induced subsets
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: Parameterizing above or below guaranteed values
cites work: Parameterized Algorithms for (r,l)-Partization
cites work: The Complexity of Enumeration and Reliability Problems
DOI: 10.1016/J.TCS.2020.09.006
Recommended article: Polynomial time algorithms for tracking path problems
Recommended article: Polynomial Time Algorithms for Tracking Path Problems
Recommended article: Fixed-parameter tractable algorithms for tracking set problems
Recommended article: A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth
Recommended article: Q5874536
Recommended article: Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
Recommended article: Structural parameterizations of Tracking Paths problem
Recommended article: On dynamic shortest paths problems
Recommended article: Algorithms – ESA 2004
Recommended article: Shortest paths algorithms: Theory and experimental evaluation
description: scientific article