Polynomial time algorithms for tracking path problems

DOI10.1007/s00453-022-00931-1OpenAlexW4210856162MaRDI QIDQ2144269

Pratibha Choudhary

Publication date: 1 June 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-00931-1

zbMATH Keywords

pathsapproximationbounded degree graphsgraphstournamentschordal graphstracking paths

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

Polynomial Time Algorithms for Tracking Path Problems

Cites Work

• The disjoint paths problem in quadratic time
• Disjoint paths in tournaments
• The directed subgraph homeomorphism problem
• Some simplified NP-complete graph problems
• Separating codes and traffic monitoring
• Tournament games and Condorcet voting
• Fixed-parameter tractable algorithms for tracking shortest paths
• Fixed-parameter tractable algorithms for tracking set problems
• The Voting Problem
• A quick method for finding shortest pairs of disjoint paths
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Finding k Disjoint Paths in a Directed Planar Graph
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Polynomial Time Algorithms for Tracking Path Problems
• Tracking Paths
• A polynomial sized kernel for tracking paths problem
• Tracking routes in communication networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Polynomial time algorithms for tracking path problems