Polynomial Time Algorithms for Tracking Path Problems

DOI10.1007/978-3-030-48966-3_13OpenAlexW3032082593MaRDI QIDQ5041188

Pratibha Choudhary

Publication date: 13 October 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

pathsapproximationbounded degree graphsgraphstournamentschordal graphstracking paths

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items (7)

How to catch marathon cheaters: new approximation algorithms for tracking paths ⋮ Polynomial time algorithms for tracking path problems ⋮ Improved kernels for tracking paths ⋮ Fixed-parameter tractable algorithms for tracking shortest 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• Disjoint paths in tournaments
• Some simplified NP-complete graph problems
• Tournament games and Condorcet voting
• Polynomial time algorithms for tracking path problems
• Fixed-parameter tractable algorithms for tracking set problems
• The Voting Problem
• Tracking Paths
• A polynomial sized kernel for tracking paths problem
• Tracking routes in communication networks

This page was built for publication: Polynomial Time Algorithms for Tracking Path Problems