1 citations · 1 across the 5 of their papers we have counts for
9 papers
On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations
Václav Blažej, Pratibha Choudhary, Dušan Knop +3
For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important a…
Polynomial Kernels for Tracking Shortest Paths
Václav Blažej, Pratibha Choudhary, Dušan Knop +3
Given an undirected graph , vertices , and an integer , Tracking Shortest Paths requires deciding whether there exists a set of vertices su…
Parameterized Complexity of Minimum Membership Dominating Set
Akanksha Agrawal, Pratibha Choudhary, N. S. Narayanaswamy +2
Given a graph and an integer , the Minimum Membership Dominating Set (MMDS) problem seeks to find a dominating set of such that for each ,…
Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set
Václav Blažej, Pratibha Choudhary, Dušan Knop +3
Consider a vertex-weighted graph with a source and a target . Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of track…
On Kernels for d-Path Vertex Cover
Radovan Červený, Pratibha Choudhary, Ondřej Suchý
In this paper we study the kernelization of the -Path Vertex Cover (-PVC) problem. Given a graph , the problem requires finding whether there exists a set of at most v…
Structural Parameterizations of Tracking Paths Problem
Pratibha Choudhary, Venkatesh Raman
Given a graph with source and destination vertices respectively, \textsc{Tracking Paths} asks for a minimum set of vertices , such that the seque…
Polynomial Time Algorithms for Tracking Path Problems
Pratibha Choudhary
Given a graph , and terminal vertices and , the TRACKING PATHS problem asks to compute a minimum number of vertices to be marked as trackers, such that the sequence of tr…
Fixed-parameter tractable algorithms for Tracking Shortest Paths
Aritra Banik, Pratibha Choudhary, Venkatesh Raman +1
We consider the parameterized complexity of the problem of tracking shortest s-t paths in graphs, motivated by applications in security and wireless networks. Given an undirected a…
Improved Kernels for Tracking Path Problem
Pratibha Choudhary, Venkatesh Raman
Tracking of moving objects is crucial to security systems and networks. Given a graph , terminal vertices and , and an integer , the \textsc{Tracking Paths} problem as…